Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs
Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs
复制标题
恒定查询仿射不变 LCC 和 LTC 的下界
DOI：
10.1145/3016802
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sivakanth Gopi
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;Sivakanth Gopi
仿射不变的代码是在有限的字段上形成矢量空间的代码，它们在坐标空间的仿射转换下是不变的。 Reed-Solomon。具有恒定查询复杂性的可校正和可局部测试的代码。 C中的代码字数最多是EXP（OK，R，|σ|（NR-1））。代码字数C最多是EXP（OK，R，|σ|（NR-2））。通过提升的仿射不合格的代码，具有相同的不对称权衡，我们的结果是非线性代码，而以前，本·萨森（Ben-Sasson）和苏丹（Random'11）（Random'11）假定了线性。傅立叶分析。定理以有限数量的低度非经典多项式近似任何有限函数，在Gowers Norm中最多误差。
Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is that they seem well suited to admit local correctors and testers. In this work, we give lower bounds on the length of locally correctable and locally testable affine-invariant codes with constant query complexity. We show that if a code C ⊂ ΣKn is an r-query affine invariant locally correctable code (LCC), where K is a finite field and Σ is a finite alphabet, then the number of codewords in C is at most exp(OK,r,|Σ|(nr−1)). Also, we show that if C ⊂ ΣKn is an r-query affine invariant locally testable code (LTC), then the number of codewords in C is at most exp(OK,r,|Σ|(nr−2)). The dependence on n in these bounds is tight for constant-query LCCs/LTCs, since Guo, Kopparty, and Sudan (ITCS’13) constructed affine-invariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas previously, Ben-Sasson and Sudan (RANDOM’11) assumed linearity to derive similar results. Our analysis uses higher-order Fourier analysis. In particular, we show that the codewords corresponding to an affine-invariant LCC/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems, which approximate any bounded function in terms of a finite number of low-degree non-classical polynomials, up to a small error in the Gowers norm.