Two New PCPs and Their Applications

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.