Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs

Authors Venkatesan Guruswami , Nicolas Resch, Chaoping Xing



PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.4.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • Department of Computer Science, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA, USA, 15213
Nicolas Resch
  • Department of Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA, USA, 15213
Chaoping Xing
  • School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore 637371

Cite AsGet BibTex

Venkatesan Guruswami, Nicolas Resch, and Chaoping Xing. Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CCC.2018.4

Abstract

For a vector space F^n over a field F, an (eta,beta)-dimension expander of degree d is a collection of d linear maps Gamma_j : F^n -> F^n such that for every subspace U of F^n of dimension at most eta n, the image of U under all the maps, sum_{j=1}^d Gamma_j(U), has dimension at least beta dim(U). Over a finite field, a random collection of d = O(1) maps Gamma_j offers excellent "lossless" expansion whp: beta ~~ d for eta >= Omega(1/d). When it comes to a family of explicit constructions (for growing n), however, achieving even modest expansion factor beta = 1+epsilon with constant degree is a non-trivial goal. We present an explicit construction of dimension expanders over finite fields based on linearized polynomials and subspace designs, drawing inspiration from recent progress on list-decoding in the rank-metric. Our approach yields the following: - Lossless expansion over large fields; more precisely beta >= (1-epsilon)d and eta >= (1-epsilon)/d with d = O_epsilon(1), when |F| >= Omega(n). - Optimal up to constant factors expansion over fields of arbitrarily small polynomial size; more precisely beta >= Omega(delta d) and eta >= Omega(1/(delta d)) with d=O_delta(1), when |F| >= n^{delta}. Previously, an approach reducing to monotone expanders (a form of vertex expansion that is highly non-trivial to establish) gave (Omega(1),1+Omega(1))-dimension expanders of constant degree over all fields. An approach based on "rank condensing via subspace designs" led to dimension expanders with beta >rsim sqrt{d} over large fields. Ours is the first construction to achieve lossless dimension expansion, or even expansion proportional to the degree.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic constructions
  • coding theory
  • linear algebra
  • list-decoding
  • polynomial method
  • pseudorandomness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Boaz Barak, Russell Impagliazzo, Amir Shpilka, and Avi Wigderson. Personal Communication to Dvir-Shpilka [6], 2004. Google Scholar
  2. Jean Bourgain. Expanders and dimensional expansion. Comptes Rendus Mathematique, 347(7-8):357-362, 2009. URL: http://dx.doi.org/10.1016/j.crma.2009.02.009.
  3. Jean Bourgain and Amir Yehudayoff. Expansion in SL₂(ℝ) and monotone expanders. Geometric and Functional Analysis, 23(1):1-41, 2013. Preliminary version in the 44th Annual ACM Symposium on Theory of Computing (STOC 2012). This work is the full version of [2]. URL: http://dx.doi.org/10.1007/s00039-012-0200-9.
  4. Zeev Dvir and Shachar Lovett. Subspace evasive sets. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 351-358. ACM, 2012. Google Scholar
  5. Zeev Dvir and Amir Shpilka. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5):1404-1434, 2007. URL: http://dx.doi.org/10.1137/05063605X.
  6. Zeev Dvir and Amir Shpilka. Towards dimension expanders over finite fields. Combinatorica, 31(3):305-320, 2011. Google Scholar
  7. Zeev Dvir and Avi Wigderson. Monotone expanders: Constructions and applications. Theory of Computing, 6(1):291-308, 2010. URL: http://dx.doi.org/10.4086/toc.2010.v006a012.
  8. Michael A Forbes and Venkatesan Guruswami. Dimension expanders via rank condensers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 800-814, 2015. Google Scholar
  9. Michael A Forbes and Amir Shpilka. On identity testing of tensors, low-rank recovery and compressed sensing. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 163-172. ACM, 2012. Google Scholar
  10. Ernst M. Gabidulin. Theory of codes with maximum rank distance. Probl. Inform. Transm., 21(1):1-12, 1985. URL: http://www.mathnet.ru/eng/ppi967.
  11. Ariel Gabizon. Deterministic extractors for affine sources over large fields. In Deterministic Extraction from Weak Random Sources, pages 33-53. Springer, 2011. Google Scholar
  12. Venkatesan Guruswami. Linear-algebraic list decoding of folded reed-solomon codes. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011, pages 77-85. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/CCC.2011.22.
  13. Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica, 36(2):161-185, 2016. Google Scholar
  14. Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Information Theory, 54(1):135-150, 2008. URL: http://dx.doi.org/10.1109/TIT.2007.911222.
  15. Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM (JACM), 56(4):20, 2009. Google Scholar
  16. Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of Reed-Solomon codes. IEEE Transactions on Information Theory, 59(6):3257-3268, 2013. Google Scholar
  17. Venkatesan Guruswami and Carol Wang. Evading subspaces over large fields and explicit list-decodable rank-metric codes. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 748-761. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.748.
  18. Venkatesan Guruswami, Carol Wang, and Chaoping Xing. Explicit list-decodable rank-metric and subspace codes via subspace designs. IEEE Transactions on Information Theory, 62(5):2707-2718, 2016. Google Scholar
  19. Venkatesan Guruswami and Chaoping Xing. Folded codes from function field towers and improved optimal rate list decoding. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 339-350. ACM, 2012. URL: http://dx.doi.org/10.1145/2213977.2214009.
  20. Venkatesan Guruswami and Chaoping Xing. List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), pages 843-852. ACM, 2013. Google Scholar
  21. Venkatesan Guruswami, Chaoping Xing, and Chen Yuan. Subspace designs based on algebraic function fields. Transactions of the AMS, 2017. To appear. Available as arXiv:1704.05992. Google Scholar
  22. Aram W. Harrow. Quantum expanders from any classical cayley graph expander. Quantum Information & Computation, 8(8-9):715-721, 2008. URL: http://www.rintonpress.com/journals/qiconline.html#v8n89.
  23. Zohar S. Karnin and Amir Shpilka. Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333-364, 2011. Google Scholar
  24. Alexander Lubotzky and Efim Zelmanov. Dimension expanders. Journal of Algebra, 319(2):730-738, 2008. Google Scholar
  25. Farzad Parvaresh and Alexander Vardy. Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 285-294, 2005. Google Scholar
  26. Pavel Pudlák and Vojtěch Rödl. Pseudorandom sets and explicit constructions of Ramsey graphs. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 327-346. Dept. Math., Seconda Univ. Napoli, Caserta, 2004. Google Scholar
  27. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics, 155(1):157-187, 2002. Google Scholar
  28. Salil P. Vadhan. Pseudorandomness. Foundations and Trendsregistered in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  29. Avi Wigderson. Expanders: Old and new applications and problems. Lecture at the Institute for Pure and Applied Mathematics (IPAM), 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail