3
$\begingroup$

I am referring to section 8.1 of this paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf. Can someone kindly give me a concrete definition of what it means to "construct a PCP" and if that is the same as a "PCP verifier". Are they the same things?

Its not clear to me as to what it means to say that "Let the bits in the proof be vertices of a graph and the tests of the verifier be the edges of the graph." How can one encode vertices of a graph as single bits?


I am trying to match this to the concepts in the lecture notes by one of the authors, https://courses.cs.washington.edu/courses/cse533/05au/ but its not clear as to how to go about doing it. If someone can help identify the correspondence that would also be a great help!

$\endgroup$
  • $\begingroup$ Have you heard about the PCP theorem? $\endgroup$ – adrianN Dec 26 '16 at 17:53
  • $\begingroup$ Yes! Thats what the attached lecture notes are about! $\endgroup$ – gradstudent Dec 26 '16 at 19:56
4
$\begingroup$

A PCP is a probabilistically checkable proof, and the PCP verifier is the algorithm that checks it. In our case, we are given an instance of Unique Label Cover which is promised to be either at least $(1-\eta)$-satisfiable (Yes instance) or at most $\gamma$-satisfiable (No instance). The (polynomial size) proof, which is similar to a witness in an NP verifier, purports to show that the instance is a Yes instance. It is given by a sequence of bits. The verifier is a probabilistic algorithm which checks the proof. If the instance is a Yes instance then there is a proof which convinces the verifier with probability at least $c$ (the completeness), and if the instance is a No instance then every proof convinces the verifier with probability at most $s$ (the soundness).

This particular verifier chooses two bits $\pi_i, \pi_j$ of the proof $\pi$ according to some complicated distribution, and checks that $\pi_i \neq \pi_j$. Every Yes instance has a proof such that $\Pi[\pi_i \neq \pi_j] \geq c$, and for No instances, all proofs satisfy $\Pr[\pi_i \neq \pi_j] \leq s$.

You can encode this verifier as an instance of Max Cut. The vertices $v_1,\ldots,v_N$ correspond to the bits of the proof $\pi_1,\ldots,\pi_N$, and two vertices $v_i,v_j$ are connected with an edge whose weight is the probability that the verifier chooses to check the two bits $\pi_i,\pi_j$. A cut in the graph can be though of encoding a proof: vertices on one side of the cut are 0 bits, and vertices on the other size are 1 bits. Under this encoding, an edge $(v_i,v_j)$ is cut iff in the corresponding proof, $\pi_i \neq \pi_j$.

The upshot is that if the Unique Label Cover instance is a Yes instance, then the Max Cut instance has a cut whose value is at least $c$, whereas if the Unique Label Cover instance is a No instance, all cuts of the Max Cut instance have value at most $s$. Therefore any approximation algorithm for Max Cut whose approximation ratio is better than $c/s$ would be able to solve Unique Label Cover, which is UGC-hard.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the reply! Let me think more about your answer and I hope to get back to you! $\endgroup$ – gradstudent Dec 27 '16 at 20:28
  • $\begingroup$ In the given lecture notes I am hard pressed to find the notion of "inner verifier" and "outer verifier" which somehow seems to be the most used terminology with regards to PCP based proofs like in the attached paper. Can you help connect this to the linked lecture notes? $\endgroup$ – gradstudent Jan 7 '17 at 20:59
  • $\begingroup$ This sounds like an altogether different question, which you are welcome to ask separately. $\endgroup$ – Yuval Filmus Jan 7 '17 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.