Hot answers tagged

10 votes
Accepted

A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut

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 $|\...
user avatar
9 votes

If SAT is in PCP, for some constant q, then P = NP

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 ...
user avatar
8 votes

Why does Dinur's proof of the PCP theorem fail to work for unique games?

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 ...
user avatar
  • 5,055
7 votes
Accepted

Best known asymptotic PCP sizes / 3-SAT

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)}...
user avatar
  • 5,055
6 votes

Results comparing BQP and NEXP

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 ...
user avatar
5 votes
Accepted

Technical lemma about curves used in original proof of PCP theorem

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$ ...
user avatar
  • 387
5 votes

PCP research proposal

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....
user avatar
  • 5,055
4 votes
Accepted

Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al

"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 ...
user avatar
  • 4,308
3 votes
Accepted

Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?

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$. ...
user avatar
3 votes

If SAT is in PCP, for some constant q, then P = NP

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 ...
user avatar
  • 1,877
3 votes
Accepted

From CHSH inequality to CHSH game

I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games ...
user avatar
2 votes

Bivariate low-degree polynomial testing of Polishchuk-Spielman

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 ...
user avatar
  • 1,877
2 votes

Is there a gap amplification type of result for the Graph Isomorphism Problem?

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 ...
user avatar
  • 2,295
1 vote

Technical issue with PCP theorem proof

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-...
user avatar
  • 51

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