Graph expansion and the unique games conjecture

By Prasad Raghavendra, David Steurer. Symposium on the Theory of Computing, 2010

298 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/14836d573c94dc8db699cd3f0a08373c50d73fc2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Subhash Khot
2. Prasad Raghavendra
3. Elchanan Mossel
4. Oded Goldreich
5. Nisheeth K. Vishnoi
6. Irit Dinur
7. Shmuel Safra

In Computer Networks and Communications

1. Subhash Khot
2. Elchanan Mossel
3. Prasad Raghavendra
4. Oded Goldreich
5. Shmuel Safra
6. Irit Dinur

Citations in the corpus

• Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry (2011, background): “Such a conjecture (see [41] for a formal statement) implies the Unique Games Conjecture as shown in [41].”