Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test

The Cube versus Cube test is a variant of the well-known Plane versus Plane test of Raz and Safra [10], in which to each 3-dimensional affine subspace C of 𝔽 n q , a polynomial of degree at most d , T ( C ), is assigned in a somewhat locally consistent manner: taking two cubes C 1 , C 2 that intersect in a plane uniformly at random, the probability that T ( C 1 ) and T ( C 2 ) agree on C 1 ∩ C 2 is at least some ε. An element of interest is the soundness threshold of this test, i.e. the smallest value of ε, such that this amount of local consistency implies a global structure; namely, that there is a global degree d function g such that g| C = T (C) for at least Ω(ε) fraction of the cubes. We show that the cube versus cube low degree test has soundness poly( d )/ q . This result achieves the optimal dependence on q for soundness in low degree testing and improves upon previous soundness results of poly( d )/ q 1/2 due to Bhangale, Dinur and Navon [4].