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/

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

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.

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.

Based on Smooth and Strong PCPs.

Powered by the Academic theme for Hugo.