Theory of Computing
-------------------
Title : On Axis-Parallel Tests for Tensor Product Codes
Authors : Alessandro Chiesa, Peter Manohar, and Igor Shinkar
Volume : 16
Number : 5
Pages : 1-34
URL : http://www.theoryofcomputing.org/articles/v016a005
Abstract
--------
$ \newcommand{\colored}{} \newcommand{\codedist}{\colored{d}}
\newcommand{\blocklength}{\colored{n}}
\newcommand{\poly}{\operatorname{poly}} $
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 Bezout'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).