2026-07-23T07:03:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17529 2024-03-06T10:59:49Z ddc:004 open_access

Rounding via Low Dimensional Embeddings Braverman, Mark Minzer, Dor Parallel Repetition Small Set Expanders Semi-Definite Programs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Braverman and Dor Minzer 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.26 urn:nbn:de:0030-drops-175291 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.26 eng https://creativecommons.org/licenses/by/4.0/legalcode