Abstract
A regular graph G = (V,E) is an (ε,γ) smallset 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 complexitytheoretic results on smallset expanders. In particular, we show:
1) MaxCut: we show that if a regular graph G = (V,E) is an (ε,γ) smallset expander that contains a cut of fractional size at least 1δ, then one can find in G a cut of fractional size at least 1O(δ/(εγ⁶)) in polynomial time.
2) Improved spectral partitioning, Cheeger’s inequality and the parallel repetition theorem over smallset expanders. The general form of each one of these results involves squareroot 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 lowdimensional space while roughly maintaining ?₂² distances, and then perform a preprocessing step using lowdimensional geometry and the properties of ?₂² distances over it. This preprocessing leverages the smallset 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 integralsolution rounding schemes.
BibTeX  Entry
@InProceedings{braverman_et_al:LIPIcs.ITCS.2023.26,
author = {Braverman, Mark and Minzer, Dor},
title = {{Rounding via Low Dimensional Embeddings}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {26:126:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17529},
URN = {urn:nbn:de:0030drops175291},
doi = {10.4230/LIPIcs.ITCS.2023.26},
annote = {Keywords: Parallel Repetition, Small Set Expanders, SemiDefinite Programs}
}
Keywords: 

Parallel Repetition, Small Set Expanders, SemiDefinite Programs 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 