Alan Guo
ABSTRACT
In this work we explore error-correcting codes derived from the "lifting" of "affine-invariant" codes. Affine-invariant codes are simply linear codes whose coordinates are a vector space over a field and which are invariant under affine-transformations of the coordinate space. Lifting takes codes defined over a vector space of small dimension and lifts them to higher dimensions by requiring their restriction to every subspace of the original dimension to be a codeword of the code being lifted. While the operation is of interest on its own, this work focusses on new ranges of parameters that can be obtained by such codes, in the context of local correction and testing. In particular we present four interesting ranges of parameters that can be achieved by such lifts, all of which are new in the context of affine-invariance and some may be new even in general. The main highlight is a construction of high-rate codes with sublinear time decoding. The only prior construction of such codes is due to Kopparty, Saraf and Yekhanin [33]. All our codes are extremely simple, being just lifts of various parity check codes (codes with one symbol of redundancy), and in the final case, the lift of a Reed-Solomon code.
We also present a simple connection between certain lifted codes and lower bounds on the size of "Nikodym sets". Roughly, a Nikodym set in Fqm is a set S with the property that every point has a line passing through it which is almost entirely contained in S. While previous lower bounds on Nikodym sets were roughly growing as qm/2m, we use our lifted codes to prove a lower bound of (1 - o(1))qm for fields of constant characteristic.
- Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Reed-Muller codes. IEEE Transactions on Information Theory, 51(11):4032--4039, 2005. Google Scholar
Digital Library
- Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge, 2009. Google ScholarDigital Library
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501--555, May 1998. Google ScholarDigital Library
- Sanjeev Arora and Madhu Sudan. Improved low degree testing and its applications. Combinatorica, 23(3):365--426, 2003. Preliminary version in Proceedings of ACM STOC 1997. Google ScholarDigital Library
- Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer. Making the long code shorter, with applications to the unique games conjecture. CoRR, abs/1111.0405, 2011.Google Scholar
- Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, and Madhu Sudan. On sums of locally testable affine invariant properties. Electronic Colloquium on Computational Complexity (ECCC), 18:79, 2011.Google Scholar
- Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, and Madhu Sudan. Symmetric LDPC codes are not necessarily locally testable. In IEEE Conference on Computational Complexity, pages 55--65. IEEE Computer Society, 2011. Google ScholarDigital Library
- Eli Ben-Sasson, Noga Ron-Zewi, and Madhu Sudan. Sparse affine-invariant linear codes are locally testable. Electronic Colloquium on Computational Complexity (ECCC), 19:49, 2012.Google Scholar
- Eli Ben-Sasson and Madhu Sudan. Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC), 17:108, 2010.Google Scholar
- Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of Reed-Muller codes. In FOCS, pages 488--497. IEEE Computer Society, 2010. Google ScholarDigital Library
- Pier Vittorio Ceccherini and J. W. P. Hirschfeld. The dimension of projective geometry codes. Discrete Mathematics, 106--107:117--126, 1992. Google ScholarDigital Library
- Zeev Dvir. On the size of Kakeya sets in finite fields. Journal of the American Mathematical Society, (to appear), 2008. Article electronically published on June 23, 2008.Google Scholar
- Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. In FOCS, pages 181--190. IEEE Computer Society, 2009. Google ScholarDigital Library
- Zeev Dvir and Amir Shpilka. An improved analysis of linear mergers. Computational Complexity, 16(1):34--59, 2007. Google ScholarDigital Library
- Zeev Dvir and Avi Wigderson. Kakeya sets, new mergers, and old extractors. SIAM J. Comput., 40(3):778--792, 2011. Google ScholarDigital Library
- Chunrong Feng, Liangpan Li, and Jian Shen. Some inequalities in functional analysis, combinatorics, and probability theory. Electr. J. Comb., 17(1), 2010.Google Scholar
- Katalin Friedl and Madhu Sudan. Some improvements to total degree tests. In Proceedings of the 3rd Annual Israel Symposium on Theory of Computing and Systems, pages 190--198, Washington, DC, USA, 4--6 January 1995. IEEE Computer Society. Corrected version available online at http://people.csail.mit.edu/madhu/papers/friedl.ps. Google ScholarDigital Library
- Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 32--42, New Orleans, Louisiana, 6--8 May 1991. Google ScholarDigital Library
- Peter Gemmell and Madhu Sudan. Highly resilient correctors for multivariate polynomials. Information Processing Letters, 43(4):169--174, September 1992. Google ScholarDigital Library
- Oded Goldreich and Tali Kaufman. Proximity oblivious testing and the role of invariances. Electronic Colloquium on Computational Complexity (ECCC), 17:58, 2010.Google Scholar
- Elena Grigorescu, Tali Kaufman, and Madhu Sudan. 2-transitivity is insufficient for local testability. In IEEE Conference on Computational Complexity, pages 259--267, 2008. Google ScholarDigital Library
- Elena Grigorescu, Tali Kaufman, and Madhu Sudan. Succinct representation of codes with applications to testing. In Proceedings of RANDOM-APPROX 2009, volume 5687 of Lecture Notes in Computer Science, pages 534--547. Springer, 2009. Google Scholar
- Alan Guo, Swastik Kopparty, and Madhu Sudan. New affine-invariant codes from lifting. CoRR, abs/1208.5413v2, 2012. Also appears as ECCC TR 12--149.Google Scholar
- Alan Guo and Madhu Sudan. Some closure features of locally testable affine-invariant properties. Electronic Colloquium on Computational Complexity (ECCC), 19:48, 2012.Google Scholar
- Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan. Absolutely sound testing of lifted codes. Manuscript, November 2012.Google Scholar
- Elad Haramaty, Amir Shpilka, and Madhu Sudan. Optimal testing of multivariate polynomials over small prime fields. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22--25, 2011, pages 629--637. IEEE, 2011. Google ScholarDigital Library
- Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman. Testing low-degree polynomials over prime fields. Random Struct. Algorithms, 35(2):163--193, 2009. Google ScholarDigital Library
- Tali Kaufman and Shachar Lovett. Testing of exponentially large codes, by a new extension to weil bound for character sums. Electronic Colloquium on Computational Complexity (ECCC), 17:65, 2010.Google Scholar
- Tali Kaufman and Alexander Lubotzky. Edge transitive ramanujan graphs and symmetric ldpc good codes. In Howard J. Karloff and Toniann Pitassi, editors, STOC, pages 359--366. ACM, 2012. Google ScholarDigital Library
- Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM Journal of Computing, 36(3):779--802, 2006. Google ScholarDigital Library
- Tali Kaufman and Madhu Sudan. Algebraic property testing: The role of invariance. Electronic Colloquium on Computational Complexity (ECCC), 14(111), 2007.Google Scholar
- Tali Kaufman and Avi Wigderson. Symmetric LDPC codes and local testing. In Andrew Chi-Chih Yao, editor, ICS, pages 406--421. Tsinghua University Press, 2010.Google Scholar
- Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. In Lance Fortnow and Salil P. Vadhan, editors, STOC, pages 167--176. ACM, 2011. Google ScholarDigital Library
- Liangpan Li. On the size of Nikodym sets in finite fields. ArXiv e-prints, March 2008.Google Scholar
- Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 475--484, New York, NY, 1997. ACM Press. Google ScholarDigital Library
- Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252--271, April 1996. Google ScholarDigital Library
- Shubhangi Saraf and Madhu Sudan. Improved lower bound on the size of Kakeya sets over finite fields. ArXiv e-prints, August 2008.Google Scholar
- K.J.C. Smith. On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry. Journal of Combinatorial Theory, 7(2):122--129, 1969.Google ScholarCross Ref
- Sergey Yekhanin. Personal communication, April 2011.Google Scholar
Index Terms
- New affine-invariant codes from lifting
Recommendations
Short locally testable codes and proofs
Studies in complexity and cryptographyWe survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Local testability refers to approximately testing large objects based on a very small number of probes,...
A `nondecimated' lifting transform
Classical nondecimated wavelet transforms are attractive for many applications. When the data comes from complex or irregular designs, the use of second generation wavelets in nonparametric regression has proved superior to that of classical wavelets. ...
Robust pcps of proximity, shorter pcps and applications to coding
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computingWe continue the study of the trade-off between the length of PCP sand their query complexity, establishing the following main results(which refer to proofs of satisfiability of circuits of size n): 1 We present PCPs of length exp(Õ(log log n)2)•n that ...
Comments