Plane vs. Plane Low Degree Test

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 F m q a bivariate degree d polynomial. The goal is to check if these polynomials are restrictions of a global degree d polynomial f : F m q → F q . Raz and Safra introduced the following natural test: sample two random planes P, P ′ intersecting in a line ℓ and check if T (P)| ℓ = T (P ′ )| ℓ , i.e., the two table entries agree on the points on ℓ.

We show that if the test passes with probability at least ε = Ω(d/q), then there is a global degree d polynomial f such that for at least Ω(ε) 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 (poly(d)/q) 1/8 . With Ω(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 = Ω(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.