Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-126 | 2nd September 2025 21:04

Plane vs. Plane Low Degree Test

RSS-Feed




TR25-126
Authors: Amey Bhangale, Silas Richelson
Publication: 2nd September 2025 22:39
Downloads: 171
Keywords: 


Abstract:

In this work, we give an optimal analysis of the plane versus plane test of Raz and Safra (STOC'97). More specifically, consider a table $T$ that assigns every plane $P$ from $\mathbb{F}_q^m$ a bivariate degree $d$ polynomial. The goal is to check if these polynomials are restrictions of a global degree $d$ polynomial $f:\mathbb{F}_q^m \rightarrow \mathbb{F}_q$. Raz and Safra introduced the following natural test: sample two random planes $P,P'$ intersecting in a line $\ell$ and check if $T(P)|_{\ell} = T(P')|_{\ell}$, \emph{i.e.}, the two table entries agree on the points on $\ell$.

We show that if the test passes with probability at least $\varepsilon=\Omega(d/q)$, then there is a global degree $d$ polynomial $f$ such that for at least $\Omega(\varepsilon)$ fraction of the planes $P$, $T(P)=f|_P$. This improves on the previous best analysis of the test by Moshkovitz and Raz (STOC'06), where they proved the soundness of the test is at least $(\text{poly}(d)/q)^{1/8}$. With $\Omega(1/q)$ as a natural lower bound on the soundness of this test, our result gets the optimal dependence on the field size, while also working for large degree parameters $d=\Omega(q)$. Our proof combines algebraic aspects from prior work on the lines vs lines test, with combinatorial aspects of recent works on the cubes vs cubes test.



ISSN 1433-8092 | Imprint