Hot answers tagged

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

The powering step fails. After the powering, each vertex is labeled with a neighborhood of the original graph. each edge checks that its endpoints agree on the intersection of their neighborhoods, and that this labeling satisfies the edges in this intersection. However, the edge cannot check anything about part of the labeling that lies outside the ...


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

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

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


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.


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

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.


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


2

If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$. But in the beginning of the proof of Lemma 8 they assume without loss of generality that $P$ and $E$ do not have a common factor. More specifically, they show that if $P$ and $E$ have a common factor then they can use induction ...


2

I do not know if such a thing could exist or not. But it is interesting (and perhaps timely) to note that such a "gap amplification" would likely imply a quasipolynomial time algorithm for graph isomorphism (different than the recently announced one) In this paper, an approximation algorithm is given for the "MAX-PGI" problem of maximizing matched pairs of ...


1

The query complexity used in this paper is $O(1)$ and $O(poly(logn))$. For Lemma 3.1 there is a note that the query complexity used is $O(1)$. If the question is how Lemma 3.1 generalizes to non-constant query complexity, this does present a problem outside of $O(poly(f(n)))$. This problem is sidestepped by composing a verifier that reduces query ...


1

There is a classical paper of Feige and Killian Zero Knowledge and the Chromatic Number that uses the ideas from Zero Knowledge Proofs in order to construct PCPs with certain "ZKP-type" properties. Using these properties they prove that it is NP-hard to color a $N^{0.01}$-colorable graph with $N^{0.99}$-colors. It should be noted that their result does not ...


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