Revised: July 22, 2020

Published: September 25, 2020

**Keywords:**tensor product codes, locally testable codes, low-degree testing, extremal graph theory,

**Categories:**error-correcting codes, tensor product codes, locally testable codes, low-degree testing, extremal graph theory

**ACM Classification:**E4, F.2.2

**AMS Classification:**68P30, 94B05, 94B25

**Abstract:**
[Plain Text Version]

Many low-degree tests examine the input function via its restrictions to random hyperplanes 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 class of codes, namely tensor product codes.
Moreover, axis-parallel tests play a key role in constructing LTCs with inverse polylogarithmic rate and short PCPs (Polishchuk, Spielman 1994; 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 the Bivariate Low-Degree Testing Theorem of Polishchuk and Spielman in the low-agreement regime, albeit
for much larger fields.
Namely, for the
tensor product of the Reed--Solomon code with itself,
we prove that for sufficiently large fields, the $2$-query variant of the axis-parallel line test (row-vs-column test) works for *arbitrarily small agreement*. Prior analyses of axis-parallel tests assumed high agreement, and no results for such tests in the low-agreement regime were known.

Our proof technique deviates significantly from that of Polishchuk and Spielman, which relies on algebraic methods such as Bézout's Theorem, and instead leverages a fundamental result in extremal graph theory by Kővári, Sós, and Turán. To our knowledge, this is the first time this result is used in the context of low-degree testing.

*(2) Improved robustness for tensor product codes.*
Robustness is a strengthening of local testability that underlies many applications. We prove that the axis-parallel hyperplane test for the
$m$-th tensor power
of a linear code with block length $\blocklength$ and distance $\codedist$ is $\Omega(\frac{\codedist^m}{\blocklength^m})$-robust. This improves on a theorem of Viderman (2012) by a factor of $1/\poly(m)$. While the improvement is not large, we believe that our proof is a notable simplification compared to prior work.

------------

A preliminary version of this paper appeared in the Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM'17).