Document Open Access Logo

Double Balanced Sets in High Dimensional Expanders

Authors Tali Kaufman, David Mass

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.3.pdf
  • Filesize: 0.65 MB
  • 17 pages

Document Identifiers

Author Details

Tali Kaufman
  • Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel
David Mass
  • Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel

Funding

  • Kaufman, Tali: Supported by ERC and BSF.
  • Mass, David: Supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities.

Cite As Get BibTex

Tali Kaufman and David Mass. Double Balanced Sets in High Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.3

Abstract

Recent works have shown that expansion of pseudorandom sets is of great importance. However, all current works on pseudorandom sets are limited only to product (or approximate product) spaces, where Fourier Analysis methods could be applied. In this work we ask the natural question whether pseudorandom sets are relevant in domains where Fourier Analysis methods cannot be applied, e.g., one-sided local spectral expanders.
We take the first step in the path of answering this question. We put forward a new definition for pseudorandom sets, which we call "double balanced sets". We demonstrate the strength of our new definition by showing that small double balanced sets in one-sided local spectral expanders have very strong expansion properties, such as unique-neighbor-like expansion. We further show that cohomologies in cosystolic expanders are double balanced, and use the newly derived strong expansion properties of double balanced sets in order to obtain an exponential improvement over the current state of the art lower bound on their minimal distance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • High dimensional expanders
  • Double balanced sets
  • Pseudorandom functions

Metrics

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

References

  1. V. L. Alev, F. G. Jeronimo, and M. Tulsiani. Approximating constraint satisfaction problems on high-dimensional expanders. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 180-201, 2019. Google Scholar
  2. V. L. Alev and L. C. Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1198-1211, 2020. Google Scholar
  3. N. Anari, V. Jain, F. Koehler, H. T. Pham, and T-D. Vuong. Entropic independence in high-dimensional expanders: Modified log-sobolev inequalities for fractionally log-concave polynomials and the ising model. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.04105.
  4. N. Anari, K. Liu, and S. Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.00303.
  5. N. Anari, K. Liu, S. Oveis Gharan, and C. Vinzant. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1-12, 2019. Google Scholar
  6. M. Bafna, M. Hopkins, T. Kaufman, and S. Lovett. Hypercontractivity on High Dimensional Expanders. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.09444.
  7. Y. Dikstein and I. Dinur. Agreement testing theorems on layered set systems. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1495-1524. IEEE, 2019. Google Scholar
  8. I. Dinur, Y. Filmus, P. Harsha, and M. Tulsiani. Explicit SoS lower bounds from high-dimensional expanders. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.05218.
  9. S. Evra and T. Kaufman. Bounded degree cosystolic expanders of every dimension. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 36-48, 2016. Google Scholar
  10. S. Evra, T. Kaufman, and G. Zemor. Decodable quantum LDPC codes beyond the √n distance barrier using high dimensional expanders. In 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020. to appear. Google Scholar
  11. M. Gromov. Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry. Geometric And Functional Analysis, 20(2):416-526, 2010. Google Scholar
  12. M. Hopkins and T-C. Lin. Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares. arXiv preprint, 2022. URL: http://arxiv.org/abs/2204.11469.
  13. T. Kaufman, D. Kazhdan, and A. Lubotzky. Ramanujan Complexes and Bounded Degree Topological Expanders. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 484-493, 2014. Google Scholar
  14. T. Kaufman and D. Mass. Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  15. P. Keevash, N. Lifshitz, E. Long, and D. Minzer. Hypercontractivity for global functions and sharp thresholds. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.05568.
  16. S. Khot, D. Minzer, D. Moshkovitz, and M. Safra. Small set expansion in the johnson graph. In Electron. Colloquium Comput. Complex., volume 25, page 78, 2018. Google Scholar
  17. S. Khot, D. Minzer, and M. Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 592-601. IEEE, 2018. Google Scholar
  18. A. Leverrier and G. Zémor. Quantum tanner codes. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.13641.
  19. N. Linial and R. Meshulam. Homological connectivity of random 2-complexes. Combinatorica, 26(4):475-487, 2006. Google Scholar
  20. P. Panteleev and G. Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.03654.
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