In Section 3.2 of On Syntactic versus Computational Views on Approximability by Khanna, et al., the authors state that an adaptation of the results from Proof Verification and Hardness of Approximation Problems by Arora, et al. proves that there is a polynomial time computable gap-introducing reduction from SAT to Max 3-SAT, and furthermore, that there is a polynomial time computable function that computes a satisfying assignment for an instance of SAT given an assignment satisfying strictly greater than $1 - \epsilon$ of the clauses of the transformed instance of Max 3-SAT, where $\epsilon$ is the gap. From what I understand, the authors claim that such a function exists because the proof by Arora, et al. utilizes an error-correcting code, so the original message (the assignment satisfying the instance of SAT) can be reconstructed from a corrupted message (the assignment satisfying greater than $1 - \epsilon$ of the clauses of Max 3-SAT). This function for reconstructing a satisfying assignment is critical for proving hardness results in classes of approximable optimization problems under approximation-preserving reductions.

Does The PCP Theorem by Gap Amplification by Dinur also imply the existence of such a function?

  • 3
    $\begingroup$ I believe so. Look at the exposition of Dinur's proof in Arora & Barak for example. You can see that the soundness part of gap amplification, the new component in Dinur's proof, is proved by decoding an assignment to the input CSP instance. In general, soundness arguments are decoding arguments, I am not aware of any exceptions $\endgroup$ Apr 8, 2013 at 23:27


Your Answer

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

Browse other questions tagged or ask your own question.