Questions tagged [pcp]
Probabilistically checkable proofs
53
questions
11
votes
1
answer
523
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 ...
- 6,470
3
votes
1
answer
81
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 ...
- 12.1k
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
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 ...
- 24.8k
6
votes
1
answer
290
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 ...
- 5,460
7
votes
1
answer
359
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'...
- 397
8
votes
2
answers
473
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 ...
- 101
12
votes
1
answer
769
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 ...
CommunityBot
- 1
4
votes
1
answer
266
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?$$
- 12.9k
9
votes
1
answer
237
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 ...
- 5,460
0
votes
1
answer
183
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 ...
- 46
1
vote
1
answer
196
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 ...
- 4,461
1
vote
1
answer
295
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 ...
- 21.6k
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 ...
CommunityBot
- 1
65
votes
11
answers
5k
views
What are good references to understanding the proof of the PCP theorem?
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
- 18.2k
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, ...
- 2,295
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 ...
- 99
4
votes
2
answers
435
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 ...
- 187
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 ...
- 187
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
9
votes
1
answer
456
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 ...
- 21.6k
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 ...
- 10.3k
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]$, ...
- 3,698
1
vote
3
answers
1k
views
PCP characterization of NP
The PCP theorem (NP= PCP(log n, O(1)) )is a major result in complexity theory with many applications such as proving hardness of approximate results. However, it seems to me that it does not offer any ...
- 20.9k
7
votes
1
answer
220
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 ...
- 18.2k
9
votes
2
answers
987
views
Quantum PCP and hardness of simulating of Hamiltonians
I have a few questions about Quantum PCP conjecture:
What is the statement of the quantum PCP conjecture?
What implications would Quantum PCP theorem have for simulating of Hamiltonians?
Is it ...
CommunityBot
- 1
3
votes
2
answers
474
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 ...
- 1,927
6
votes
2
answers
207
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,496
2
votes
2
answers
513
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 ...
- 705
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 ...
- 21.6k
1
vote
1
answer
367
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 ?
- 1,178
6
votes
4
answers
805
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 ...
- 158
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
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
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
10
votes
1
answer
573
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 \...
CommunityBot
- 1
20
votes
3
answers
802
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 ...
- 11k
3
votes
1
answer
407
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 ...
- 13.6k
0
votes
1
answer
535
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 ...
- 21.6k
17
votes
2
answers
898
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"?
- 216
13
votes
1
answer
254
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 $\...
CommunityBot
- 1
10
votes
2
answers
474
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 ...
- 11k
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 ...
- 1,311
4
votes
1
answer
315
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 ...
- 11k
2
votes
1
answer
207
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-...
- 21.6k
8
votes
1
answer
427
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 ...
- 27.5k
8
votes
1
answer
421
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)| = ...
- 11k
12
votes
3
answers
537
views
Hard gaps in maximum constraint satisfaction problems?
An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $...
- 20.9k
6
votes
1
answer
432
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 ...
- 651