Talks

Rigid Matrices From Rectangular PCPs

In this talk, I will focus on introducing and motivating rectangular PCPs, and their application to matrix rigidity. No prior knowledge in PCPs is assumed. Based on “Rigid Matrices From Rectangular PCPs”, Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal, 2020. https://eccc.weizmann.ac.il/report/2020/075/

Rigid Matrices From Rectangular PCPs

Based on “Rigid Matrices From Rectangular PCPs”, Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal, 2020. https://eccc.weizmann.ac.il/report/2020/075/

Smooth and Strong PCPs

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and any incorrect claim is rejected with high probability regardless of the given alleged proof. But what about incorrect proofs of correct claims? In a strong PCP, an alleged proof is rejected with probability proportional to its distance from a correct proof. For applications to hardness of approximation, it is useful to have strong PCPs in which each bit in the proof is equally likely to be queried.

Smooth and Strong PCPs

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and any incorrect claim is rejected with high probability regardless of the given alleged proof. But what about incorrect proofs of correct claims? In a strong PCP, an alleged proof is rejected with probability proportional to its distance from a correct proof. For applications to hardness of approximation, it is useful to have strong PCPs in which each bit in the proof is equally likely to be queried.

Incorrect (Probabilistic) Proofs for Correct Claims: Smooth and Strong PCPs

Based on Smooth and Strong PCPs.