# Tag Info

Accepted

• 5,055

### 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 ...
• 1,679
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$ ...
• 387

### 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....
• 5,055
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 ...
• 4,308
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$. ...

### 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 ...
• 1,877
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 ...
• 23.5k

### 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 ...
• 1,877

### 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 ...
• 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-...
• 51

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