Chiesa, Alessandro ;
Manohar, Peter ;
Shinkar, Igor
On AxisParallel Tests for Tensor Product Codes
Abstract
Many lowdegree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the linevsline (Arora, Sudan 2003), planevsplane (Raz, Safra 1997), and cubevscube (Bhangale, Dinur, Livni 2017) tests.
In this paper we study tests that only consider restrictions along axisparallel hyperplanes, which have been studied by Polishchuk and Spielman (1994) and BenSasson and Sudan (2006). While such tests are necessarily "weaker", they work for a more general class of codes, namely tensor product codes. Moreover, axisparallel tests play a key role in constructing LTCs with inverse polylogarithmic rate and short PCPs (Polishchuk, Spielman 1994; BenSasson, Sudan 2008; Meir 2010). We present two results on axisparallel tests.
(1) Bivariate lowdegree testing with lowagreement. We prove an analogue of the Bivariate LowDegree Testing Theorem of Polishchuk and Spielman in the lowagreement regime, albeit with much larger field size. Namely, for the 2wise tensor product of the ReedSolomon code, we prove that for sufficiently large fields, the 2query variant of the axisparallel line test (rowvscolumn test) works for arbitrarily small agreement. Prior analyses of axisparallel tests assumed high agreement, and no results for such tests in the lowagreement 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 Kovari, Sos, and Turan. To our knowledge, this is the first time this result is used in the context of lowdegree testing.
(2) Improved robustness for tensor product codes. Robustness is a strengthening of local testability that underlies many applications. We prove that the axisparallel hyperplane test for the mwise tensor product of a linear code with block length n and distance d is Omega(d^m/n^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.
BibTeX  Entry
@InProceedings{chiesa_et_al:LIPIcs:2017:7588,
author = {Alessandro Chiesa and Peter Manohar and Igor Shinkar},
title = {{On AxisParallel Tests for Tensor Product Codes}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {39:139:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7588},
URN = {urn:nbn:de:0030drops75882},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.39},
annote = {Keywords: tensor product codes, locally testable codes, lowdegree testing, extremal graph theory}
}
2017
Keywords: 

tensor product codes, locally testable codes, lowdegree testing, extremal graph theory 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

2017 