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$.
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$.
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$.
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$.
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$.
Included a soundness lower bound construction and showed that ? is the optimal exponent.
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.
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.