Skip to main content
Source Link
Joe Bebel
  • 2.3k
  • 18
  • 18

In a lecture by Madhu Sudan* he claimed there was some belief that there exists $s > 1/2$ such that $\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$, via semidefinite programming, prior to the proof of Håstad's three bit PCP theorem.

Indeed SDP does show $\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$, giving a tight bound on the complexity of such PCPs.

(*I found this lecture of Madhu published in "Computational Complexity Theory edited by Rudich/Wigderson")

Post Made Community Wiki by Joe Bebel