Questions tagged [pcp]
Probabilistically checkable proofs
55 questions
3
votes
0
answers
87
views
What does Håstad verifier query?
I am learning about Håstad 3-Query PCP theorem so what follows reflects my poor understanding of the subject.
I am slightly confused by the 3-queries that the verifier does to check if a given $\...
- 61
5
votes
1
answer
716
views
PCP without reading the statement
The PCP theorem (very imprecisely!) states that for every $x\in L\in NP$ there is a polynomial witness $w$ such that for some random algorithm it is enough to read a constant number of bits of $w$ to ...
- 14.2k
3
votes
1
answer
123
views
Application of PCP and error correcting codes to LLMs?
Are there any interesting results in applying error correcting codes and ideas from PCP (Probabilistically Checkable Proofs) to improve the quality of large language models (LLM), or connecting them ...
- 21.8k
1
vote
0
answers
148
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
8
votes
1
answer
314
views
Why does Dinur's proof of the PCP theorem fail to work for unique games?
What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ...
- 81
7
votes
1
answer
363
views
Technical lemma about curves used in original proof of PCP theorem
I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn'...
- 153
4
votes
1
answer
274
views
Results comparing BQP and NEXP
Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$
- 13.3k
12
votes
1
answer
778
views
Technical issue with PCP theorem proof
I am reading the proof from here and I stumbled upon a technical (yet crucial) problem. I know this is rather specific and the context is problematic, but I couldn't figure it out myself.
In pages 51 ...
- 153
9
votes
1
answer
252
views
Best known asymptotic PCP sizes / 3-SAT
What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
- 2,742
0
votes
1
answer
201
views
Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?
Something has been buzzing me recently. It is well-known that $\textbf{PCP}[poly(n), 0] = \textbf{coRP}$, but does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$ ?
I have found a proof for this ...
- 13
1
vote
1
answer
204
views
Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al
This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say ...
- 103
1
vote
1
answer
300
views
PCP research proposal [closed]
Hi I am taking an undergraduate taking a course in Probabilistic checkable Proofs. I will greatly appreciate if you can suggest some good research ideas and pertaining reading for someone who is just ...
- 39
3
votes
0
answers
90
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
195
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
127
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 ...
- 393
4
votes
0
answers
166
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
1
vote
0
answers
71
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
9
votes
1
answer
531
views
A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut
I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence ...
- 1,328
5
votes
3
answers
1k
views
If SAT is in PCP, for some constant q, then P = NP
I have seen this statement before, but I haven't really seen a proof of it:
If $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, for some constant $q$, then $P = NP$.
Now, if $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, ...
- 679
7
votes
1
answer
228
views
Can NP-hard statements be proved by PCPs that only involve reading 2 bits?
For non-negative integers q, let PCP(q) denote the set of promise problems
that have polynomial-length probabalistically checkable proofs
over the binary alphabet in which the verifier only reads q ...
user6973
3
votes
1
answer
1k
views
From CHSH inequality to CHSH game
I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
- 661
3
votes
2
answers
534
views
How are PCPs and ZKPs related?
I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge ...
- 841
8
votes
2
answers
539
views
Bivariate low-degree polynomial testing of Polishchuk-Spielman
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 ...
- 81
6
votes
2
answers
209
views
Is a software implementation of a PCP encoder available?
We all know the PCP Theorem. Is there any software package availalbe taking a CNF in e.g. DIMACS format as input, and producing a PCP encoding in the same format as output? It might be interesting to ...
- 5,576
2
votes
2
answers
543
views
Multi prover, verifier games and PCP theorem
This question came up while I was going through Siu On Chan's paper on Approximation Resistance. My question is not really related to the paper though. I also guess that this is more of a reference ...
- 23
1
vote
1
answer
392
views
number of PCP queries
we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?
6
votes
4
answers
812
views
How to start studying topics Hardness of approximation and PCP's
Recently I have done an introductory course on complexity theory ( which covered 90% of sipser text book). Now I would like to study the topics Hardness of approximation and PCP's. Can you please ...
- 2,044
7
votes
0
answers
349
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,291
4
votes
0
answers
106
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,291
37
votes
4
answers
4k
views
Hardness of approximation without the PCP theorem
An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any ...
- 11.4k
21
votes
3
answers
826
views
$\mathcal{MA}$ in terms of $\mathcal{PCP}$
The probabilistic proof system $\mathcal{PCP}[f(n),g(n)]$ is commonly referred to as a restriction of $\mathcal{MA}$, where Arthur can only use $f(n)$ random bits and can only examine $g(n)$ bits of ...
- 745
10
votes
1
answer
591
views
One-sided errors in probablistic proof systems
In most probabilistic proof systems ( PCP theorem, for instance), the error-probabilities are usually defined on the side of the false-positives, i.e., a typical definition could look like : if $x \...
- 486
11
votes
1
answer
538
views
Connection between PCP and L=SL
The book by Arora and Barak contains in chapter notes on PCP
We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's ...
- 1,281
20
votes
0
answers
489
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,291
3
votes
1
answer
416
views
Consequences of Unique Games being a NPI problem
Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so UGC is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation ...
- 47
0
votes
1
answer
558
views
Non adaptive PCP
So this is a question from Arora, Barak textbook which was on our homework. I submitted it so no worries. :)
The question asks us to simulate an adaptive PCP with a non-adaptive one. It says this can ...
- 117
13
votes
1
answer
256
views
Is there a continuous version of parallel repetition theorem
Raz's Parallel pretition theorem is an important result in PCP, inapproximation, etc. The theorem is fomalized as follows.
A game $G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)$, where $\...
- 425
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
10
votes
2
answers
488
views
Do good PCPs for NP give us good PCPs for the entire polynomial hierarchy?
The PCP Theorem states that every decision problem in NP has probabilistically checkable proofs (or equivalently, that there exists a complete and quasi-sound proof system for theorems in NP using ...
- 2,055
20
votes
2
answers
1k
views
Super-polynomial time approximation algorithms for MAX 3SAT
The PCP theorem states that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.
There is a ...
- 21.1k
4
votes
2
answers
446
views
On the need for a self-correcting function in the PCP theorem
Original proof of the PCP theorem, uses self-correction property of linear functions.
Assume we have $f: \{0,1\}^n \rightarrow \{0,1\}$, a function or table of values,
that is $(1-\delta)$-close to ...
- 705
54
votes
1
answer
2k
views
Is there a gap amplification type of result for the Graph Isomorphism Problem?
Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, ...
- 619
4
votes
1
answer
327
views
Effect of serial repetition on soundness of a PCP, and what is special with 1/2?
As far as I know, following operations convert a $PCP_{1,s}[O(\log n),O(1)]$ , to a $PCP_{1,s’}[O(\log n),O(1)]$, with following $s’$ :
By constant number of applications of serial repetition: can ...
- 705
2
votes
1
answer
212
views
hardness of approximation result for a Min-CSP, by reduction from PCPs
Reduction from PCPs allow us to prove hardness of approximation results for a number of constraint satisfaction problems. I've seen such a reductions only for Max-CSPs. Is this possible only for Max-...
- 705
8
votes
1
answer
434
views
Approximating Random MAX-k-SAT
It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity.
Should ...
- 1,224
8
votes
1
answer
427
views
Degree reduction step in Dinur's proof of the PCP theorem
In the degree reduction step of Dinur's proof, the input graph $G$ is transformed into a graph $G'$ by replacing each vertex $v \in V(G)$ by a set of vertices, $cloud(v)$, such that $|cloud(v)| = ...
user1694
17
votes
2
answers
925
views
Is there a simple argument that shows that the unique games conjecture implies the PCP theorem
how can one show that what is relation between "Unique games conjecture" and "PCP theorem"?
how does one explain "Unique games conjecture" is stronger form of "PCP theorem"?
- 705
7
votes
1
answer
449
views
Alphabet Reduction Step in PCP Proof
I understand that the purpose of the alphabet reduction step in Dinur's proof of the PCP theorem is to reduce the alphabet after the graph powering stage. However, I don't see why the alphabet needs ...
user934
11
votes
1
answer
709
views
PCP Theorem - Alphabet Reduction Step
What follows might seem stupid (and that probably reflects my poor understanding - so please bear with me)
I had a query on PCP theorem. We know that after the first three steps viz. Degree Reduction,...
- 1,983
6
votes
2
answers
464
views
PCPs with imperfect completeness
The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify ...
- 2,492