I read about modifications of the low-degree test used in the (first) proof of the PCP theorem. The test used in the proof works over randomly chosen lines while modifications allow choosing random planes (or affine subspaces in general). Is it possible to use these modifications in the framework (low-degree extensions and sum-checking) of the proof of the PCP theorem? Does this involve major changes?

EDIT: In the paper [1] by Raz and Safra it is stated that the scheme of the old proof is insufficient when one wants to achieve a sub-constant error. So what if one is satisfied by the "old" constant error? Does the (Hyper-)Plane-Point Test work for that? I have seen proofs using this test to show $NP \subseteq PCP[log(n), polylog(n)]$ but I have never seen the final argument for $NP = PCP[log(n), 1]$ via proof composition.

[1] A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP


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.