Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #6 to TR26-147 | 4th November 2026 06:22

Cube-Root Soundness Is Optimal for the Line–versus–Point Test

RSS-Feed




Revision #6
Authors: Quang Dao, Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Accepted on: 4th November 2026 06:22
Downloads: 92
Keywords: 


Abstract:

The line-versus-point test, studied by Rubinfeld and Sudan (1996) and Arora and Sudan (2003), takes as input a point table $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ and a polynomial $P_L$ of degree at most $d$ for each affine line $L$. It samples a uniformly random incident pair $(x,L)$ such that $x\in L$ and checks if $f(x)=P_L(x)$. This test and its variants have played a central role in PCP constructions. A well-studied quantitative question about this test is the following. What is the largest exponent $\tau\gt0$ for which there are constants $C,c\gt0$ such that acceptance $\varepsilon\ge C(d/q)^\tau$ guarantees agreement at least $c\varepsilon$ with a polynomial of total degree at most $d$, over all finite fields, dimensions $m\ge2$, and degrees $1\le d\lt q$?

We characterize the optimal soundness exponent of this test, showing that it is exactly $1/3$. More specifically, over every finite field $\mathbb{F}_q$, for every $m\ge2$ and $d\ge1$, whenever a point table and a degree-$d$ line table pass the test with probability $\varepsilon$, there is a polynomial $Q$ of total degree at most $d$ such that $\Pr_{x\in\mathbb{F}_q^m}[Q(x)=f(x)]\ge\varepsilon-C(d/q)^{1/3}$, where $C\gt0$ is an absolute constant.

The previous best bounds, due to Harsha, Kumar, Saptharishi, and Sudan (2024), are soundness thresholds $\Omega((d/q)^{1/48})$ for $m\gt2$ and $\Omega((d/q)^{1/7})$ for $m=2$.

To complement this upper bound, we give an explicit construction in every dimension $m\ge 3$ over cubic extension fields of size $q=s^3$, where $s\ge3$ is a prime power. For every $1\le d\le q$, our constructed tables have acceptance $d/q+(1-d/q)q^{-1/3}+O(q^{-2/3})$, while every polynomial of total degree at most $d$ agrees with the point table on at most a $d/q+O(q^{-2/3})$ fraction of points. Thus global agreement is a vanishing fraction of acceptance whenever $d=o(q^{2/3})$. In particular, no soundness exponent larger than $1/3$ is possible, even for a fixed degree $d$.


Revision #5 to TR26-147 | 3rd November 2026 08:16

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





Revision #5
Authors: Quang Dao, Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Accepted on: 3rd November 2026 08:16
Downloads: 41
Keywords: 


Abstract:

The line-versus-point test, studied by Rubinfeld and Sudan (1996) and Arora and Sudan (2003), takes as input a point table $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ and a polynomial $P_L$ of degree at most $d$ for each affine line $L$. It samples a uniformly random incident pair $(x,L)$ such that $x\in L$ and checks if $f(x)=P_L(x)$. This test and its variants have played a central role in PCP constructions. A well-studied quantitative question about this test is the following. What is the largest exponent $\tau\gt0$ for which there are constants $C,c\gt0$ such that acceptance $\varepsilon\ge C(d/q)^\tau$ guarantees agreement at least $c\varepsilon$ with a polynomial of total degree at most $d$, over all finite fields, dimensions $m\ge2$, and degrees $1\le d\lt q$?

We characterize the optimal soundness exponent of this test, showing that it is exactly $1/3$. More specifically, over every finite field $\mathbb{F}_q$, for every $m\ge 2$ and $d\ge 1$, whenever a point table and a degree-$d$ line table pass the test with probability $\varepsilon$, there is a polynomial $Q$ of total degree at most $d$ such that $\Pr_{x\in\mathbb{F}_q^m}[Q(x)=f(x)]\ge\varepsilon-C(d/q)^{1/3}$, where $C\gt 0$ is an absolute constant.

The previous best bounds, due to Harsha, Kumar, Saptharishi, and Sudan (2024), are soundness thresholds $\Omega((d/q)^{1/48})$ for $m\gt2$ and $\Omega((d/q)^{1/7})$ for $m=2$.

To complement this upper bound, we give an explicit construction in every dimension $m\ge3$ over cubic extension fields of size $q=s^3$, where $s\ge3$ is a prime power. For every $1\le d\le q$, our constructed tables have acceptance $d/q+(1-d/q)q^{-1/3}+O(q^{-2/3})$, while every polynomial of total degree at most $d$ agrees with the point table on at most a $d/q+O(q^{-2/3})$ fraction of points. Thus global agreement is a vanishing fraction of acceptance whenever $d=o(q^{2/3})$. In particular, no soundness exponent larger than $1/3$ is possible, even for a fixed degree $d$.


Revision #4 to TR26-147 | 3rd November 2026 08:11

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





Revision #4
Authors: Quang Dao, Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Accepted on: 3rd November 2026 08:11
Downloads: 23
Keywords: 


Abstract:

The line-versus-point test, studied by Rubinfeld and Sudan (1996) and Arora and Sudan (2003), takes as input a point table $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ and a polynomial $P_L$ of degree at most $d$ for each affine line $L$. It samples a uniformly random incident pair $(x,L)$ such that $x\in L$ and checks if $f(x)=P_L(x)$. This test and its variants have played a central role in PCP constructions. A well-studied quantitative question about this test is the following. What is the largest exponent $\tau>0$ for which there are constants $C,c>0$ such that acceptance $\varepsilon\ge C(d/q)^\tau$ guarantees agreement at least $c\varepsilon$ with a polynomial of total degree at most $d$, over all finite fields, dimensions $m\ge2$, and degrees $1\le d 0$ is an absolute constant.

The previous best bounds, due to Harsha, Kumar, Saptharishi, and Sudan (2024), are soundness thresholds $\Omega((d/q)^{1/48})$ for $m>2$ and $\Omega((d/q)^{1/7})$ for $m=2$.

To complement this upper bound, we give an explicit construction in every dimension $m\ge3$ over cubic extension fields of size $q=s^3$, where $s\ge3$ is a prime power. For every $1\le d\le q$, our constructed tables have acceptance $d/q+(1-d/q)q^{-1/3}+O(q^{-2/3})$, while every polynomial of total degree at most $d$ agrees with the point table on at most a $d/q+O(q^{-2/3})$ fraction of points. Thus global agreement is a vanishing fraction of acceptance whenever $d=o(q^{2/3})$. In particular, no soundness exponent larger than $1/3$ is possible, even for a fixed degree $d$.


Revision #3 to TR26-147 | 3rd November 2026 08:11

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





Revision #3
Authors: Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Accepted on: 3rd November 2026 08:11
Downloads: 31
Keywords: 


Abstract:

The line-versus-point test, studied by Rubinfeld and Sudan (1996) and Arora and Sudan (2003), takes as input a point table $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ and a polynomial $P_L$ of degree at most $d$ for each affine line $L$. It samples a uniformly random incident pair $(x,L)$ such that $x\in L$ and checks if $f(x)=P_L(x)$. This test and its variants have played a central role in PCP constructions. A well-studied quantitative question about this test is the following. What is the largest exponent $\tau>0$ for which there are constants $C,c>0$ such that acceptance $\varepsilon\ge C(d/q)^\tau$ guarantees agreement at least $c\varepsilon$ with a polynomial of total degree at most $d$, over all finite fields, dimensions $m\ge2$, and degrees $1\le d 0$ is an absolute constant.

The previous best bounds, due to Harsha, Kumar, Saptharishi, and Sudan (2024), are soundness thresholds $\Omega((d/q)^{1/48})$ for $m>2$ and $\Omega((d/q)^{1/7})$ for $m=2$.

To complement this upper bound, we give an explicit construction in every dimension $m\ge3$ over cubic extension fields of size $q=s^3$, where $s\ge3$ is a prime power. For every $1\le d\le q$, our constructed tables have acceptance $d/q+(1-d/q)q^{-1/3}+O(q^{-2/3})$, while every polynomial of total degree at most $d$ agrees with the point table on at most a $d/q+O(q^{-2/3})$ fraction of points. Thus global agreement is a vanishing fraction of acceptance whenever $d=o(q^{2/3})$. In particular, no soundness exponent larger than $1/3$ is possible, even for a fixed degree $d$.


Revision #2 to TR26-147 | 3rd November 2026 08:06

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





Revision #2
Authors: Quang Dao, Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Accepted on: 3rd November 2026 08:06
Downloads: 30
Keywords: 


Abstract:

The line-versus-point test, studied by Rubinfeld and Sudan (1996) and Arora and Sudan (2003), takes as input a point table $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ and a polynomial $P_L$ of degree at most $d$ for each affine line $L$. It samples a uniformly random incident pair $(x,L)$ such that $x\in L$ and checks if $f(x)=P_L(x)$. This test and its variants have played a central role in PCP constructions. A well-studied quantitative question about this test is the following. What is the largest exponent $\tau>0$ for which there are constants $C,c>0$ such that acceptance $\varepsilon\ge C(d/q)^\tau$ guarantees agreement at least $c\varepsilon$ with a polynomial of total degree at most $d$, over all finite fields, dimensions $m\ge2$, and degrees $1\le d0$ is an absolute constant.

The previous best bounds, due to Harsha, Kumar, Saptharishi, and Sudan (2024), are soundness thresholds $\Omega((d/q)^{1/48})$ for $m>2$ and $\Omega((d/q)^{1/7})$ for $m=2$.

To complement this upper bound, we give an explicit construction in every dimension $m\ge3$ over cubic extension fields of size $q=s^3$, where $s\ge3$ is a prime power. For every $1\le d\le q$, our constructed tables have acceptance $d/q+(1-d/q)q^{-1/3}+O(q^{-2/3})$, while every polynomial of total degree at most $d$ agrees with the point table on at most a $d/q+O(q^{-2/3})$ fraction of points. Thus global agreement is a vanishing fraction of acceptance whenever $d=o(q^{2/3})$. In particular, no soundness exponent larger than $1/3$ is possible, even for a fixed degree $d$.



Changes to previous version:

Included a soundness lower bound construction and showed that ? is the optimal exponent.


Revision #1 to TR26-147 | 16th August 2026 19:54

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





Revision #1
Authors: Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Accepted on: 16th August 2026 19:54
Downloads: 1073
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.


Paper:

TR26-147 | 13th August 2026 17:27

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





TR26-147
Authors: Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Publication: 16th August 2026 15:29
Downloads: 985
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