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 ...


29

One can get a $7/8+\varepsilon/8$ approximation for MAX3SAT that runs in $2^{O(\varepsilon n)}$ time without too much trouble. Here is the idea. Divide the set of variables into $O(1/\varepsilon)$ groups of $\varepsilon n$ variables each. For each group, try all $2^{\varepsilon n}$ ways to assign the variables in the group. For each reduced formula, run the ...


19

The related $2-1$-conjecture of Khot implies the PCP theorem with perfect completeness: The proof is expected to give a labeling of the vertices. The verifier selects a random edge queries its endpoints and accepts iff the constraint holds. For getting a PCP theorem with perfect completeness from the unique games conjecture you need to, as Boaz writes, ...


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 ...


18

To somewhat restate what Ryan Williams wrote in his last paragraph: The Moshkovitz-Raz theorem shows that there is a function $T(n) = 2^{n^{1-o(1)}}$ such that if Max-3Sat can be $(7/8 + 1/(\log \log n)^{.000001})$-approximated in time $T(n)$ then the decision version of 3Sat is in time $2^{o(n)}$. It is commonly believed that the latter is impossible (...


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

The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2δ$ for all $x$ (not only random $x$)


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

Does exponential decrease also happen in continuous case? No. Feige and Verbitsky [FV02] showed that for every n, there is a game G (with finite sets of questions and answers) such that v(G)≤3/4 and v(Gn)≥1/8. Because your formulation generalizes games with finite sets of questions and answers of any size, parallel repetition (of any finitely many times) ...


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

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 ...


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. ...


6

Let me try to clarify. Consider the following computational problem: given a mathematical statement (in your favorite axiom system) and a number n given in unary representation, decide whether the statement has a proof of size n. This is an NP problem: given a proof, one can efficiently verify that it is of size n and that it is a valid proof of the ...


6

The truth of a statement is different from it having a (short) proof in a proof system. The language is expressive but it doesn't mean that all valid statements in the language have short proofs in the system. The theorem doesn't say that you can check the truth of a statement or even the correctness of an arbitrary long proof or of arbitrary theorems. It ...


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-...


4

To address your revised question: If UGC is false, is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover? If it were known that it is NP-hard to approximate VC better than a factor of 2, even if the UGC is false, then we would unconditionally know that approximating VC to a factor better than 2 is NP-hard. This ...


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-\...


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