Hot answers tagged

35

An example is this paper: Guruswami, V., & Khanna, S. (2004). On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1): 30-40. link Using the PCP-Theorem, Khanna, Linial, and Safra (2000) proved that it is NP-hard to color a 3-colorable graph using just 4 colors. Later, Guruswami & Khanna (2004) gave, among ...


18

If you want to restate the definition of MA in terms of PCP, you need another parameter for PCP, namely the proof length. MA is clearly the same as PCP with polynomial randomness, polynomial queries, and polynomial-length proofs. Usually the proof length in PCP is not restricted (that is, it is bounded only implicitly by randomness and queries), but this ...


15

For the maximum edge disjoint paths problem in directed graphs the paper of Ma & Wang (2000) was based on the label cover problem which in turn is based on the PCP theorem. Subsequently a simple reduction via the 2-disjointpath problem hardness was found by Guruswami et. al. (2003) which gave improved hardness as well.


13

There are examples from approximate counting. Approximately counting the number of satisfying assignments of an NP-relation can only be harder than deciding whether a satisfying assignment exists, so it's not too surprising that one doesn't need the PCP theorem to prove hardness for such problems. Still, the PCP theorem sometimes gives a convenient starting ...


12

Allowing completeness error has no problem, and it is often considered. Here are some pointers. On the other hand, generally speaking, disallowing soundness error removes the power of a model significantly. In the case of interactive proof systems, disallowing soundness error renders interaction useless except for one-way communication from a prover to a ...


12

The precise answer to your question is given by Oded Goldreich in his article "Bravely, Moderately: A Common Theme in Four Recent Works". Here is the link: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf


11

Tsuyoshi Ito answered the question literally, but I wanted to comment about the semantics of MA and PCP and how they differ. MA is the probabilistic version of NP, i.e., the verifier gets to also use poly-many random bits. In PCP we may refer to the "randomness" of the verifier, but usually the randomness is logarithmic in the running time of the verifier, ...


11

Under a hardness assumption, namely, that the complexity class $E = DTIME(2^{O(n)})$ requires circuits of exponential size, suffices to derandomize $MA$, so that $MA = NP$. In fact, the derandomization is to show that $BPP = P$ (see Impagliazzo-Wigderson or Sudan-Trevisan-Vadhan) . But since in $MA$ the verifier is a $BPP$ machine, we can replace it with a ...


10

Another answer, which is in a somewhat different spirit than the previous answers, is this paper of Uri Feige: Relations between Average Case Complexity and Approximation Complexity. Uri shows that average case assumptions can replace the PCP theorem for proving hardness of approximation of some problems. Note, however, that we don't know how to prove the ...


10

Let me see if I can clarify this, on a high level. Assume the UG instance is a bipartite graph $G = (V \cup W, E)$, bijections $\{\pi_e\}_{e \in E}$, where $\pi_e\colon \Sigma \to \Sigma$, and $|\Sigma| = m$. You want to construct a new graph $H$ so that if the UG instance is $1-\delta$ satisfiable, then $H$ has a large cut, and if the UG instance is not ...


9

Given a CSP where all constraints have arity at most $q$ we want to distinguish between the case where everything is satisfiable and the case where at most $1/2^q$ fraction of the constraints are satisfiable, in polynomial time. Here is how this can be done. First, all predicates used in the CSP must have at least one satisfying assignment (otherwise we ...


8

Such a characterization of NP follows from the NP-hardness of any gap problem for a binary CSP with constraints of arity 2. A binary CSP with arity 2 constraints is given by a family $\Pi$ of arity 2 relations on $\{0, 1\}^n$. An instance is given by a set of constraints. The GapCSP$_\Pi$($c$,$s$) problem for the CSP is the promise problem of distinguishing ...


7

The state-of-the-art for PCPs that yield a reduction to $(\frac{7}{8}+\varepsilon)$ 3-SAT (even for sub-constant $\varepsilon$) are those of Dana Moshkovitz and Ran Raz, which have length $n^{1 + o(1)}$. I do not know, however, if anyone tried to compute the exact dependence of the length on $\varepsilon$, or the computation complexity of the reduction. ...


7

I recommend Lectures on Proof Verification and Approximation Algorithms, E.W.Mayr and H.J.Prömel and A.Steger (Eds.), Lecture Notes in Computer Science, vol. 1367, Springer Verlag 1998. These lectures are very suitable for studying these topics from the basic.


7

As suggested by Kaveh, the relevant chapters in Arora-Barak are a good starting point. Soon you'll want to sink your teeth into a significant paper. One difficulty you may encounter is that recent papers in this area build on two decades worth of intense research, which can be intimidating to a beginner. IMHO, the best balance between importance of results ...


7

Let me sketch the relation between the PCP theorem and 2-provers 1-round game. For concreteness let's consider the MAX-3-SAT problem. In this problem we are given a 3-CNF formula, and our goal is to find an assignment that maximizes the number of satisfied clauses. This problem is NP-hard, and (the CSP view of) the PCP theorem says that given a satisfiable ...


6

Basically everything that is known about the Quantum PCP conjecture has been collected in this survey by Dorit Aharonov, Itai Arad, and Thomas Vidick: The Quantum PCP Conjecture See also Thomas' blog post on the topic.


6

The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding any oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such an oracle last year. In summary, the oracle you ask for currently is not known to exist, but people are looking. There are oracles relative to which $P\ne BPP=...


5

Eli Ben-Sasson's group is working on implementing PCPs. You can e-mail him and ask for their code.


5

There has been some recent effort to make PCPs practical for use in verifying outsourced computation. Check the work by this UT Austin group for example: http://www.cs.utexas.edu/pepper/.


5

Here are some recent papers on PCPs with small query complexity that I found interesting: arxiv.org/pdf/1305.1979 eccc.hpi-web.de/report/2013/179/download wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf eccc.weizmann.ac.il/report/2015/085 cs.utexas.edu/~danama/papers/par-rep/final3.pdf cs.utexas.edu/~danama/papers/par-rep-limit/paper.pdf eccc.hpi-...


5

Notation: Let $P(\langle x_1,\dots,x_k\rangle)$ the set of degree $k$ curves that evaluates to $x_1,\dots,x_k\in\mathbb{F}^m$ at the first $k$ field elements in $\mathbb{F}$ and we will use just $P$ as a shorthand for this set. Let $S$ be any subset of $ \mathbb{F}^m$. Below, we assume that multiplicity is taken into account when set cardinalities are ...


4

"So, applying MIS on $g$" To apply the Majority is Stablest theorem, you need to apply it to a non-negative parameter $\rho'\in[0,1)$ (read the statement of the theorem). Since in Proposition 7.3 the parameter $\rho\in(-1,0]$ is non-positive, this means you here apply it to $\rho' \stackrel{\rm def}{=} -\rho\in[0,1)$, giving $$\mathbb{S}_{-\rho}(g) \leq 1-\...


3

Recall PCP theorem, $PCP(log(n), 1)$ is NP already and actually $PCP(poly(n),1)$ is $NEXP$. The problem of your proof is that you cannot simulate a coRP algorithm on a string with length only $2^q$. Though it will only access q bits, the bits it accesses to depend on the random coins. You should not think of a specific coin outcome but all of them on a ...


3

The algorithm is as follows: If one of the constraints has no satisfying assignments, then output NO. Otherwise, output YES Obviously this can be done in polynomial time. For the analysis note that if one of the constraints has no satisfying assignments, then clearly the given instance is not satisfiable. Otherwise, if all constraints are satisfiable, ...


3

PCPs are very often used to construct ZKPs, especially for NP-complete languages. The idea is simple: you commit to every bit of PCP separately, and then the prover makes random queries to the PCP. Given the query and committed bit, you prove in ZK that the bits in concrete locations would make the prover to accept. Since the number of queries is small, the ...


3

So first, there is the class called IP, see e.g., http://en.wikipedia.org/wiki/IP_(complexity). The trouble with verifying is, of course, that the Prover might lie. Now, imagine that you can ask two Provers, who are not allowed to talk to each other, then they might give a different answer to the same question and be caught! This class is called MIP, and is ...


3

I believe the best result (with regards to the number of queries) is still Håstad's 3-query PCP. So if you choose at least 3, then it's a definite yes. These lecture slides might be a bit more useful as they cut straight to the chase.


2

Here is what we used for our seminars: Theory Reading Group: PCPs and Hardness of Approximation - Fall 2010. Arora and Barak is a good starting point.


2

It's not enough for a self study, but the notes from this DIMACS workshop might help: http://arxiv.org/pdf/1002.3864v1.pdf. Then there is Arora-Barak: http://www.cs.princeton.edu/theory/complexity/ (there is a draft online, and, as it is a draft, it has some typos).


Only top voted, non community-wiki answers of a minimum length are eligible