# Tagged Questions

Probabilistically checkable proofs

45 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 ...
105 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 ...
76 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 ...
60 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 ...
241 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 ...
452 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]$, ...
142 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 ...
737 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 ...
125 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 ...
93 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 ...
148 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 ...
308 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 ...
154 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 ?
681 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 ...
242 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 ...
88 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 ...
3k 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 ...
407 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 ...
345 views

736 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 ...
377 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 ...
887 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 ...
390 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 ...
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, ...
206 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 ...
154 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-...
263 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 ...
337 views

738 views

### PCP theorem and proof complexity?

It is known that if $P=NP$ then $CoNP= PCP[O(log(n)),O(1)]$. Also, it is known that $NEXP=PCP[poly(n),poly(n)]$. It appears that PCP can't tell us which natural problems are not in $NP$. I wonder if ...
781 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 ...
2k 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 NP = PCP(O(log(n)),O(1))). ...