摘要：Many low-degree tests examine the input function via its restrictions to randomhyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003),plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Navon 2017) tests.In this paper we study tests that only consider restrictions along axis-parallel hyperplanes,which have been studied by Polishchuk and Spielman (1994) and Ben-Sasson and Sudan(2006). While such tests are necessarily “weaker,” they work for a more general classof codes, namely tensor product codes. Moreover, axis-parallel tests play a key role inconstructing LTCs with inverse polylogarithmic rate and short PCPs (Polishchuk, Spielman1994; Ben-Sasson, Sudan 2008; Meir 2010). We present two results on axis-parallel tests.(1) Bivariate low-degree testing with low agreement. We prove an analogue of theBivariate Low-Degree Testing Theorem of Polishchuk and Spielman in the low-agreementregime, albeit for much larger fields. Namely, for the tensor product of the Reed–Solomoncode with itself, we prove that for sufficiently large fields, the 2 -query variant of the axis-parallellinetest(row-vs-columntest)worksforarbitrarilysmallagreement. Prioranalysesofaxis-parallel tests assumed high agreement, and no results for such tests in the low-agreementregime were known.Our proof technique deviates significantly from that of Polishchuk and Spielman, whichrelies on algebraic methods such as Bézout’s Theorem, and instead leverages a fundamentalresult in extremal graph theory by K˝ ovári, Sós, and Turán. To our knowledge, this is the firsttime this result is used in the context of low-degree testing.(2) Improved robustness for tensor product codes. Robustness is a strengthening of localtestability that underlies many applications. We prove that the axis-parallel hyperplane testfor the m -th tensor power of a linear code with block length n and distance d is Ω(d m /n m ) -robust. This improves on a theorem of Viderman (2012) by a factor of 1/poly(m) . Whilethe improvement is not large, we believe that our proof is a notable simplification comparedto prior work.
