Questions tagged [pcp]
Probabilistically checkable proofs
10
questions with no upvoted or accepted answers
20
votes
0
answers
480
views
Interesting PCP characterization of classes smaller than P?
The PCP theorem, $\mathsf{NP} = \mathsf{PCP}(\mathsf{log}\, n, 1)$, involves probabilistically checkable proofs with polynomial time verifiers, so the smallest class that can be characterized in this ...
- 2,281
7
votes
0
answers
348
views
Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?
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 ...
- 2,281
4
votes
0
answers
145
views
Low-degree testing in PCP Theorem using bivariate polynomials
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 ...
- 41
4
votes
0
answers
104
views
What is the query and randomness complexity for very efficient PCPs?
In the 2012 paper On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs, the authors state the following (paraphrased from page 11).
Theorem 1 (informal). There is a PCP system ...
- 2,281
4
votes
0
answers
1k
views
More legent proof of MIP=NEXP using the PCP theorem
Can we prove $\mathsf{MIP}=\mathsf{NEXP}$ using the PCP theorem $\mathsf{NP}=\mathsf{PCP(log(n),O(1))}$ as a shortcut?
$\mathsf{MIP}$ is the class of languages with multi-prover interactive proof ...
- 61
3
votes
0
answers
88
views
Non-trivial PCP characterizations of complexity classes beyond ELEMENTARY?
There are interesting results of the form $PCP[a(n), b(n)] = \texttt{SOMECLASS(n)}$ for multiple classes in the exponential hierarchy: the most famous one is probably $PCP[O(log(n)), O(1)] = NP$.
Are ...
- 281
2
votes
0
answers
187
views
hardness of approximating clique: how using FGLSS reduction with PCP verifier of hastad
I try to understand the $n^{1-\epsilon}$ hardness of approximating clique for any $\epsilon$ provided in [1]: www.nada.kth.se/~johanh/cliqueinap.ps
In fact, I only want to understand the proof of ...
- 137
2
votes
0
answers
126
views
Universal constant for bivariate testing
In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate ...
- 383
1
vote
0
answers
147
views
Looking for an implementation of any PCP-verifier for any NP problem
Is there any implementation of any PCP-verifier (for any NP problem) researchers can download and test? No matter if it is a github entry with actual downloadable code or just a (reasonably detailed) ...
- 408
1
vote
0
answers
68
views
Testing - Correcting Pairs in PCPs
The BLR linearity test and the low degree test are two common tools in PCPs. By my understanding these tests ensure bounds such that (self-) correctors can be applied. I have two questions regarding ...
- 11