11
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"...
- 5,675
10
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 ...
- 5,675
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)}...
- 5,675
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 ...
- 2,204
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$ ...
- 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....
- 5,675
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 ...
- 4,491
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 ...
- 25k
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$. ...
- 46
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 (...
- 12.4k
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 ...
- 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-...
- 51
Only top scored, non community-wiki answers of a minimum length are eligible