Crash Course on Probabilistically Checkable Proofs (PCP): Optimal Inapproximability Results
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28
summary
Claim: assuming the Unique Games Conjecture, it is NP‑hard to beat the Goemans-Williamson ~0.878 approximation for Max‑Cut. The reduction replaces each Unique‑Game vertex by a long code block and adds noisy tests whose acceptance equals noise‑stability of Boolean functions; analysis uses the invariance principle to move to Gaussian space and then Gaussian isoperimetry to show only dictator‑like functions pass the test, so any better approximation would yield a good Unique‑Game solution.
AI-written summary · about