This talk introduces Self-Proving models, a new class of models that formally prove the correctness of their outputs via an Interactive Proof system. After reviewing some related literature, I will formally define Self-Proving models and their …
I will present two relatively new types of Probabilistically Checkable Proofs (PCPs) and their various applications.
Smooth and Strong PCPs and their applications to hardness of approximation under (Bilu—Linial) stability guarantees. Rectangular PCPs and their applications to matrix rigidity. No prior knowledge of any of the above topics (especially PCPs) is expected. Based, in part, on a joint work with Amey Bhangale, Prahladh Harsha, and Avishay Tal.
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.