2022/11/17 by Mark Braverman, Dor Minzer, Braverman, Mark +1
Computer Science · Materials Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Quasicrystal Structures and Properties
paper · pdf · doi:10.48550/arxiv.2211.09729
openalex publication_date 2022/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(\fracδεγ6) 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.