Near Optimal Alphabet-Soundness Tradeoff PCPs
Tuesday, September 24, 2024 - 4:15pm to 5:15pm
Refreshments:
4:00 PM
Location:
32-G449 (Kiva/Patil)
Speaker:
Kai Zhe Zheng
Biography:
https://sites.google.com/view/kaics/home
Seminar group:
We show a nearly optimal alphabet-soundness tradeoff for NP-hardness of 2-Prover-1-Round Games (2P1R). More specifically, we show that for all \eps > 0, for sufficiently large M, it is NP-hard to decide whether a 2P1R instance of alphabet size M has value nearly 1 or at most M^{-1+\eps}. 2P1R are equivalent to 2-Query PCP, and are widely used in obtaining hardness of approximation results. As such, our result implies the following: 1) hardness of approximating Quadratic Programming within a factor of nearly log(n), 2) hardness of approximating d-bounded degree 2-CSP within a factor of nearly d/2, and 3) improved hardness of approximation results for various k-vertex connectivity problems. For the first two applications, our results nearly match the performance of the best known algorithms.
Joint work with Dor Minzer.