TY - GEN
T1 - Rounding via Low Dimensional Embeddings
AU - Braverman, Mark
AU - Minzer, Dor
N1 - Funding Information:
Funding Mark Braverman: 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. Dor Minzer: Supported by a Sloan Research Fellowship.
Publisher Copyright:
© Mark Braverman and Dor Minzer; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - 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 (Equation presented) 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 ℓ22 distances, and then perform a pre-processing step using low-dimensional geometry and the properties of ℓ22 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.
AB - 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 (Equation presented) 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 ℓ22 distances, and then perform a pre-processing step using low-dimensional geometry and the properties of ℓ22 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.
KW - Parallel Repetition
KW - Semi-Definite Programs
KW - Small Set Expanders
UR - http://www.scopus.com/inward/record.url?scp=85147539801&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85147539801&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2023.26
DO - 10.4230/LIPIcs.ITCS.2023.26
M3 - Conference contribution
AN - SCOPUS:85147539801
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
A2 - Kalai, Yael Tauman
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Y2 - 10 January 2023 through 13 January 2023
ER -