# Graph expansion and the unique games conjecture

@inproceedings{Raghavendra2010GraphEA, title={Graph expansion and the unique games conjecture}, author={Prasad Raghavendra and David Steurer}, booktitle={STOC '10}, year={2010} }

The edge expansion of a subset of vertices S ⊆ V in a graph G measures the fraction of edges that leave S. In a d-regular graph, the edge expansion/conductance Φ(S) of a subset S ⊆ V is defined as Φ(S) = (|E(S, V\S)|)/(d|S|). Approximating the conductance of small linear sized sets (size δ n) is a natural optimization question that is a variant of the well-studied Sparsest Cut problem. However, there are no known algorithms to even distinguish between almost complete edge expansion (Φ(S) = 1… Expand

#### Topics from this paper

#### 231 Citations

The Complexity of Approximating Vertex Expansion

- Mathematics, Computer Science
- 2013 IEEE 54th Annual Symposium on Foundations of Computer Science
- 2013

Under the Small Set Expansion (SSE) hypothesis, it is hard to find a subset with expansion less than C(√(ΦV log d)) for an absolute constant C, and the results suggest that vertex expansion is harder to approximate than edge expansion. Expand

Hardness of Bipartite Expansion

- Mathematics, Computer Science
- ESA
- 2016

The hardness of approximation for Bipartite Expansion is shown, which is a vertex expansion analogue of the Small Set (Edge) Expansion Conjecture of Raghavendra and Steurer 2010. Expand

Finding Sparse Cuts via Cheeger Inequalities for Higher Eigenvalues

- 2012

Cheeger’s fundamental inequality states that any edge-weighted graph has a vertex subset S such that its expansion (a.k.a. conductance of S or the sparsity of the cut (S, S̄)) is bounded as follows:… Expand

On the complexity of unique games and graph expansion

- Mathematics
- 2010

Understanding the complexity of approximating basic optimization problems is one of the grand challenges of theoretical computer science. In recent years, a sequence of works established that Khot’s… Expand

Finding Small Sparse Cuts by Random Walk

- Mathematics, Computer Science
- APPROX-RANDOM
- 2012

Using ideas developed in local graph partitioning algorithms, the following bicriteria approximation algorithms are obtained for the small sparsest cut problem, which is to find a set S ⊆ V with minimum conductance among all sets with volume at most k. Expand

On set expansion problems and the small set expansion conjecture

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2015

We study two problems related to the Small Set Expansion Conjecture?(Raghavendra and Steurer, 2010): the Maximum weight m ' -edge cover(MWEC)?problem and the Fixed cost minimum edge… Expand

Decomposing a graph into expanding subgraphs

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2018

A hereditary family of graphs with vertex separators of size n/(logn)1−o(1) such that not all graphs in the family have O(n) edges, and shows that one cannot guarantee a better vertex expansion even if allowing the average degree to be O(1). Expand

Computational topology and the Unique Games Conjecture

- Computer Science, Mathematics
- SoCG
- 2018

It is proved that inapproximability for Maximum Section of a Covering Space on (cell decompositions of) closed 2-manifolds is also equivalent to the Unique Games Conjecture, which gives the first new "Unique Games-complete" problem in over a decade. Expand

Decomposing a Graph Into Expanding Subgraphs

- Computer Science, Mathematics
- SODA
- 2015

The results imply that the eigenspace enumeration approach of Arora-Barak-Steurer cannot give (even quasi-) polynomial time algorithms for unique games. Expand

Subexponential Algorithms for U G and Related Problems

- 2010

We give subexponential time approximation algorithms for U G and the S-S E. Specifically, for some absolute constant c, we give: 1. An exp(kn)-time algorithm that, given as… Expand

#### References

SHOWING 1-10 OF 43 REFERENCES

Improved Algorithms for Unique Games via Divide and Conquer

- Computer Science
- Electron. Colloquium Comput. Complex.
- 2010

Two new approximation algorithms for Unique Games based on new methods for partitioning graphs by cutting small fractions of edges when the graph can be embedded in a suitable metric space are presented. Expand

Expander flows, geometric embeddings and graph partitioning

- Mathematics, Computer Science
- JACM
- 2009

An interesting and natural “approximate certificate” for a graph's expansion, which involves embedding an n-node expander in it with appropriate dilation and congestion, is described. Expand

Near-optimal algorithms for unique games

- Mathematics, Computer Science
- STOC '06
- 2006

This work presents significantly improved approximation algorithms for unique games that are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. Expand

Rounding Parallel Repetitions of Unique Games

- Mathematics, Computer Science
- 2008 49th Annual IEEE Symposium on Foundations of Computer Science
- 2008

It is proved that for every l epsi N, if sdpval(G) ges 1-delta, then val(Gl) gES 1-radicsldelta, giving a counterexample to the strong parallel repetition conjecture. Expand

The geometry of graphs and some of its algorithmic applications

- Computer Science, Mathematics
- Comb.
- 1995

Efficient algorithms for embedding graphs low-dimensionally with a small distortion, and a new deterministic polynomial-time algorithm that finds a (nearly tight) cut meeting this bound. Expand

On the optimality of the random hyperplane rounding technique for MAX CUT

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2002

There are graphs and optimal embeddings for which the best hyperplane approximates opt within a ratio no better than α, even in the presence of additional valid constraints, which strengthens a result of Karloff that applied only to the expected number of edges cut by a random hyperplane. Expand

How to Round Any CSP

- Computer Science, Mathematics
- 2009 50th Annual IEEE Symposium on Foundations of Computer Science
- 2009

An efficient rounding scheme is presented that achieves the integrality gap of this basic SDP relaxation for every CSP, and it also achieves the gap of much stronger SDP relaxations. Expand

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1

- Mathematics, Computer Science
- FOCS
- 2005

This paper disproves the non-uniform version of Arora, Rao and Vazirani's Conjecture (2004), asserting that the integrality gap of the sparsest cut SDP, with the triangle inequality constraints, is bounded from above by a constant. Expand

The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

- Computer Science, Mathematics
- 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
- 2005

This paper disproves the non-uniform version of Arora, Rao and Vazirani's Conjecture (2004), asserting that the integrality gap of the sparsest cut SDP, with the triangle inequality constraints, is bounded from above by a constant. Expand

Optimal algorithms and inapproximability results for every CSP?

- Computer Science, Mathematics
- STOC
- 2008

A generic conversion from SDP integrality gaps to UGC hardness results for every CSP is shown, which achieves at least as good an approximation ratio as the best known algorithms for several problems like MaxCut, Max2Sat, MaxDiCut and Unique Games. Expand