Rounding via Low Dimensional Embeddings

Mark Braverman, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 (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.

Original languageEnglish (US)
Title of host publication14th Innovations in Theoretical Computer Science Conference, ITCS 2023
EditorsYael Tauman Kalai
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772631
DOIs
StatePublished - Jan 1 2023
Event14th Innovations in Theoretical Computer Science Conference, ITCS 2023 - Cambridge, United States
Duration: Jan 10 2023Jan 13 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume251
ISSN (Print)1868-8969

Conference

Conference14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Country/TerritoryUnited States
CityCambridge
Period1/10/231/13/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Parallel Repetition
  • Semi-Definite Programs
  • Small Set Expanders

Fingerprint

Dive into the research topics of 'Rounding via Low Dimensional Embeddings'. Together they form a unique fingerprint.

Cite this