Skip to main content
Share Your Experience: Take the 2024 Developer Survey
10 votes
Accepted

PCP without reading the statement

In the standard definition of a PCP, the verifier reads the entire input $x$. Nevertheless, there is a variant of a PCP, called a "PCP of Proximity" (PCPP) or an "assignment tester"...
Or Meir's user avatar
  • 5,615
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 ...
Or Meir's user avatar
  • 5,615
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)}...
Or Meir's user avatar
  • 5,615
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 ...
Lieuwe Vinkhuijzen's 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$ ...
A.2's user avatar
  • 397
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....
Or Meir's user avatar
  • 5,615
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 ...
Clement C.'s user avatar
  • 4,471
4 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 ...
Peter Shor 's user avatar
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$. ...
WuHongxun's user avatar
2 votes

Application of PCP and error correcting codes to LLMs?

I'm not aware of any such research. I'm familiar with two standard datasets for evaluating the effectiveness of LLMs at solving math problems: GSM8K (Cobbe et al, arXiv:2110.14168) and MATH (...
D.W.'s user avatar
  • 12.1k
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 ...
Igor Shinkar's user avatar
  • 1,927
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-...
Lem's user avatar
  • 51

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