BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY: Near-Optimal Alphabet Soundness Tradeoff PCPs - Kai Zhe Zheng (MI
 T)
DTSTART:20250121T140000Z
DTEND:20250121T150000Z
UID:TALK226117@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:We show a nearly optimal alphabet-soundness tradeoff for NP-ha
 rdness 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 whe
 ther 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 obta
 ining hardness of approximation results. As such\, our result implies the 
 following: 1) hardness of approximating Quadratic Programming within a fac
 tor 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 app
 lications\, our results nearly match the performance of the best known alg
 orithms.\n\nJoint work with Dor Minzer.
LOCATION:Computer Laboratory\, William Gates Building\, FW26
END:VEVENT
END:VCALENDAR