Document Open Access Logo

Dimension Expanders via Rank Condensers

Authors Michael A. Forbes, Venkatesan Guruswami

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.800.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Michael A. Forbes
Venkatesan Guruswami

Cite As Get BibTex

Michael A. Forbes and Venkatesan Guruswami. Dimension Expanders via Rank Condensers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 800-814, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.800

Abstract

An emerging theory of "linear algebraic pseudorandomness: aims to understand the linear algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets.  In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension expanders, seeded rank condensers, two-source rank condensers, and rank-metric codes.  In particular, with the recent construction of near-optimal subspace designs by Guruswami and Kopparty as a starting point, we construct good (seeded) rank condensers (both lossless and lossy versions), which are a small collection of linear maps F^n to F^t for t<<n such that for every subset of F^n of small rank, its rank is preserved (up to a constant factor in the lossy case) by at least one of the maps. 

We then compose a tensoring operation with our lossy rank condenser to construct constant-degree dimension expanders over polynomially large fields. That is, we give a constant number of explicit linear maps A_i from F^n to F^n such that for any subspace V of F^n of dimension at most n/2, the dimension of the span of the A_i(V) is at least (1+Omega(1)) times the dimension of V. Previous constructions of such constant-degree dimension expanders were based on Kazhdan's property T (for the case when F has characteristic zero) or monotone expanders (for every field F); in either case the construction was harder than that of usual vertex expanders. Our construction, on the other hand, is simpler.

For two-source rank condensers, we observe that the lossless variant (where the output rank is the product of the ranks of the two sources) is equivalent to the notion of a linear rank-metric code. For the lossy case, using our seeded rank condensers, we give a reduction of the general problem to the case when the sources have high (n^Omega(1)) rank. When the sources have constant rank, combining this with an "inner condenser" found by brute-force leads to a two-source rank condenser with output length nearly matching the probabilistic constructions.

Subject Classification

Keywords
  • dimension expanders
  • rank condensers
  • rank-metric codes
  • subspace designs
  • Wronskians

Metrics

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

References

  1. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth-Δ formulas. In Proceedings of the \nth\intcalcSub20131968 Annual ACM Symposium on Theory of Computing (STOC 2013), pages 321-330, 2013. Full version at http://arxiv.org/abs/1209.2333. Google Scholar
  2. Boaz Barak, Russell Impagliazzo, Amir Shpilka, and Avi Wigderson. Personal Communication to Dvir-Shpilka [Dvir and Shpilka, 2011], 2004. Google Scholar
  3. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. J. ACM, 57(4), 2010. Preliminary version in the \nth\intcalcSub20051968 Annual ACM Symposium on Theory of Computing (STOC 2005). Google Scholar
  4. Jean Bourgain and Amir Yehudayoff. Expansion in SL₂(ℝ) and monotone expanders. Geometric and Functional Analysis, 23(1):1-41, 2013. Preliminary version in the \nth\intcalcSub20121968 Annual ACM Symposium on Theory of Computing (STOC 2012). This work is the full version of [Bourgain, 2009]. Google Scholar
  5. Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the \nth\intcalcSub20021968 Annual ACM Symposium on Theory of Computing (STOC 2002), pages 659-668, 2002. Google Scholar
  6. Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. J. ACM, 60(5):31, 2013. Preliminary version in the \nth\intcalcSub20121968 Annual ACM Symposium on Theory of Computing (STOC 2012). Google Scholar
  7. 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. Preliminary version in the \nth\intcalcSub20051968 Annual ACM Symposium on Theory of Computing (STOC 2005). Google Scholar
  8. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the \nth\intcalcSub20141968 Annual ACM Symposium on Theory of Computing (STOC 2014), pages 867-875, 2014. Full version at http://arxiv.org/abs/1309.5668. Google Scholar
  9. Michael A. Forbes and Amir Shpilka. On identity testing of tensors, low-rank recovery and compressed sensing. In Proceedings of the \nth\intcalcSub20121968 Annual ACM Symposium on Theory of Computing (STOC 2012), pages 163-172, 2012. Full version at http://arxiv.org/abs/1111.0663. Google Scholar
  10. Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415-440, 2008. Preliminary version in the \nth\intcalcSub20051959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005). Google Scholar
  11. Venkatesan Guruswami. Linear-algebraic list decoding of folded reed-solomon codes. In Proceedings of the \ifnumcomp2011>1995\nth\intcalcSub20111985 Annual IEEE Conference on Computational Complexity (CCC 2011)\nth\intcalcSub20111985 Annual Structure in Complexity Theory Conference (CCC 2011), pages 77-85, 2011. The full version of this paper is merged into Guruswami-Wang [Guruswami and Wang, 2013]. Google Scholar
  12. Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica, pages 1-25, 2014. Preliminary version in the \nth\intcalcSub20131959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013). Google Scholar
  13. 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. Preliminary versions appeared in Proceedings of the \ifnumcomp2011>1995\nth\intcalcSub20111985 Annual IEEE Conference on Computational Complexity (CCC 2011)\nth\intcalcSub20111985 Annual Structure in Complexity Theory Conference (CCC 2011) and Proceedings of the \nth\intcalcSub20111996 International Workshop on Randomization and Computation (RANDOM 2011). Google Scholar
  14. Venkatesan Guruswami and Carol Wang. Evading subspaces over large fields and explicit list-decodable rank-metric codes. In Proceedings of the \nth\intcalcSub20141996 International Workshop on Randomization and Computation (RANDOM 2014), pages 748-761, 2014. Full version at http://arxiv.org/abs/1311.7084. Google Scholar
  15. Venkatesan Guruswami and Chaoping Xing. Folded codes from function field towers and improved optimal rate list decoding. In Proceedings of the \nth\intcalcSub20121968 Annual ACM Symposium on Theory of Computing (STOC 2012), pages 339-350, 2012. Full version at http://arxiv.org/abs/1204.4209. Google Scholar
  16. Venkatesan Guruswami and Chaoping Xing. List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound. In Proceedings of the \nth\intcalcSub20131968 Annual ACM Symposium on Theory of Computing (STOC 2013), pages 843-852, 2013. Full version in the http://eccc.hpi-web.de/report/2012/146/. Google Scholar
  17. Aram W. Harrow. Quantum expanders from any classical cayley graph expander. Quantum Information & Computation, 8(8-9):715-721, 2008. Google Scholar
  18. 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. Preliminary version in the \ifnumcomp2008>1995\nth\intcalcSub20081985 Annual IEEE Conference on Computational Complexity (CCC 2008)\nth\intcalcSub20081985 Annual Structure in Complexity Theory Conference (CCC 2008). Google Scholar
  19. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. arXiv, 1404.4506, 2014. Google Scholar
  20. Alexander Lubotzky and Efim Zelmanov. Dimension expanders. J. Algebra, 319(2):730-738, 2008. Google Scholar
  21. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. Preliminary version in the \nth\intcalcSub20061973 International Colloquium on Automata, Languages and Programming (ICALP 2006). Google Scholar
  22. 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
  23. Ran Raz. Extractors with weak random seeds. In Proceedings of the \nth\intcalcSub20051968 Annual ACM Symposium on Theory of Computing (STOC 2005), pages 11-20, 2005. Full version in the http://eccc.hpi-web.de/report/2004/099/. Google Scholar
  24. Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Comput. Complex., 14(1):1-19, April 2005. Preliminary version in the \ifnumcomp2004>1995\nth\intcalcSub20041985 Annual IEEE Conference on Computational Complexity (CCC 2004)\nth\intcalcSub20041985 Annual Structure in Complexity Theory Conference (CCC 2004). Google Scholar
  25. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):2070-388, 2010. Google Scholar
  26. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact