Document Open Access Logo

Rounding via Low Dimensional Embeddings

Authors Mark Braverman, Dor Minzer

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.26.pdf
  • Filesize: 0.88 MB
  • 30 pages

Document Identifiers

Author Details

Mark Braverman
  • Department of Computer Science, Princeton University, NJ, USA
Dor Minzer
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Braverman, Mark: Research supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.
  • Minzer, Dor: Supported by a Sloan Research Fellowship.

Cite As Get BibTex

Mark Braverman and Dor Minzer. Rounding via Low Dimensional Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 26:1-26:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.26

Abstract

A regular graph G = (V,E) is an (ε,γ) small-set expander if for any set of vertices of fractional size at most ε, at least γ of the edges that are adjacent to it go outside. In this paper, we give a unified approach to several known complexity-theoretic results on small-set expanders. In particular, we show:  
1) Max-Cut: we show that if a regular graph G = (V,E) is an (ε,γ) small-set expander that contains a cut of fractional size at least 1-δ, then one can find in G a cut of fractional size at least 1-O(δ/(εγ⁶)) in polynomial time.
2) Improved spectral partitioning, Cheeger’s inequality and the parallel repetition theorem over small-set expanders. The general form of each one of these results involves square-root loss that comes from certain rounding procedure, and we show how this can be avoided over small set expanders.  Our main idea is to project a high dimensional vector solution into a low-dimensional space while roughly maintaining 𝓁₂² distances, and then perform a pre-processing step using low-dimensional geometry and the properties of 𝓁₂² distances over it. This pre-processing leverages the small-set expansion property of the graph to transform a vector valued solution to a different vector valued solution with additional structural properties, which give rise to more efficient integral-solution rounding schemes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Discrete optimization
Keywords
  • Parallel Repetition
  • Small Set Expanders
  • Semi-Definite Programs

Metrics

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

References

  1. Noga Alon and Bo'az Klartag. Economical toric spines via cheeger’s inequality. Journal of Topology and Analysis, 1(02):101-111, 2009. Google Scholar
  2. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 21-28, 2008. URL: https://doi.org/10.1145/1374376.1374380.
  3. Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer. Rounding parallel repetitions of unique games. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 374-383, 2008. URL: https://doi.org/10.1109/FOCS.2008.55.
  4. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 335-340, 2015. URL: https://doi.org/10.1145/2746539.2746565.
  5. Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. The grothendieck constant is strictly smaller than krivine’s bound. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 453-462, 2011. URL: https://doi.org/10.1109/FOCS.2011.77.
  6. Mark Braverman and Dor Minzer. Optimal tiling of the euclidean space using permutation-symmetric bodies. In 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), pages 5:1-5:48, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.5.
  7. Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999. Google Scholar
  8. Uriel Feige, Guy Kindler, and Ryan O'Donnell. Understanding parallel repetition requires understanding foams. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pages 179-192. IEEE, 2007. Google Scholar
  9. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  10. Thomas Holenstein. Parallel repetition: Simplification and the no-signaling case. Theory Comput., 5(1):141-172, 2009. URL: https://doi.org/10.4086/toc.2009.v005a008.
  11. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  12. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767-775, 2002. URL: https://doi.org/10.1145/509907.510017.
  13. Guy Kindler, Anup Rao, Ryan O'Donnell, and Avi Wigderson. Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM, 55(10):90-97, 2012. URL: https://doi.org/10.1145/2347736.2347757.
  14. Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. Improved cheeger’s inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 11-20, 2013. Google Scholar
  15. James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1-30, 2014. Google Scholar
  16. Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Many sparse cuts via higher eigenvalues. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1131-1140, 2012. Google Scholar
  17. Dana Moshkovitz. Strong parallel repetition for unique games on small set expanders. CoRR, abs/2103.08743, 2021. URL: http://arxiv.org/abs/2103.08743.
  18. Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 755-764, 2010. URL: https://doi.org/10.1145/1806689.1806792.
  19. Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM J. Comput., 40(6):1871-1891, 2011. URL: https://doi.org/10.1137/080734042.
  20. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. URL: https://doi.org/10.1137/S0097539795280895.
  21. Shmuel Safra and Oded Schwartz. On parallel-repetition, Unique-Games and Max-Cut, 2007. Google Scholar
  22. Luca Trevisan. Max cut and the smallest eigenvalue. SIAM J. Comput., 41(6):1769-1786, 2012. URL: https://doi.org/10.1137/090773714.
  23. Madhur Tulsiani, John Wright, and Yuan Zhou. Optimal strong parallel repetition for projection games on low threshold rank graphs. In International Colloquium on Automata, Languages, and Programming, pages 1003-1014. Springer, 2014. 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