Fall 2020

Crash Course on Probabilistically Checkable Proofs (PCP): Optimal Inapproximability Results

Monday, Aug. 24, 2020 9:00 am10:00 am

Add to Calendar



This crash course will cover the basics of PCP and highlight its connections with geometry. While it's recommended to watch all four talks, the bulk of each talk is designed as a stand-alone. 

Unique Games Conjecture, long code, max-cut hardness and isoperimetry, invariance principle, embedding.