Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-147 | 13th August 2026 17:27

Improved Soundness for the Line--versus--Point Test

RSS-Feed




TR26-147
Authors: Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Publication: 16th August 2026 15:29
Downloads: 43
Keywords: 


Abstract:

The line--versus--point test asks the following local-to-global question. Suppose a function $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ is, on average over a random affine line $L$, correlated with some degree-$d$ polynomial on $L$. Must $f$ then be globally correlated with a single multivariate polynomial of degree at most $d$? Beyond being a natural combinatorial question, this test and its variants have played a central role in the construction of PCPs.

Generally, one is most interested in the soundness of the test: the smallest expected local agreement from which one can still deduce nontrivial global agreement. We revisit the line--versus--point test and prove the following cubic threshold. If
\[
\Pr_{L,,x\in L}\bigl[P_L(x)=f(x)\bigr]\ge C\left(\frac{d}{q}\right)^{1/3},
\]
then there is a polynomial $Q\in\mathbb{F}_q[X_1,\ldots,X_m]$ of total degree at most $d$ such that
\[
\Pr_{x\in\mathbb{F}_q^m}[Q(x)=f(x)]\ge c\cdot \Pr_{L,,x\in L}\bigl[P_L(x)=f(x)\bigr],
\]
for absolute constants $C,c>0$ and over every finite field $\mathbb{F}_q$. The prior state of the art, due to [HKSS24], had an inexplicit exponent in their soundness, which we estimate to be $\Omega\left((d/q)^{1/48}\right)$ in the $m>2$ case and $\Omega\left((d/q)^{1/7}\right)$ in the $m=2$ case. We believe our proof is comparatively direct and isolates the combinatorial and algebraic mechanisms responsible for the improved soundness.



ISSN 1433-8092 | Imprint