The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 1 (Extended Abstract)
By Subhash Khot, Nisheeth K. Vishnoi. 2005
130 citations recorded by the source corpus.
View Paper: https://www.semanticscholar.org/paper/2837b20682f447647e73ba8e0ddcacd8fb56cda4
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Nisheeth K. Vishnoi
- Subhash Khot
- Prasad Raghavendra
- Elchanan Mossel
- Oded Goldreich
- L. Elisa Celis
- Irit Dinur
- Guy Kindler
Citations in the corpus
- Towards Sharp Inapproximability For Any 2-CSP (2007, unknown): “Examples of such results include 2 − hardness for VERTEX COVER [32], superconstant hardness for SPARSESTCUT [10, 33] and MULTICUT [10], 1/2 + hardness of MAXIMUM ACYCLIC SUBGRAPH [23], hardness of approximating M AX INDEPENDENT SET within d/poly(log d) in degreed graphs [42], and approximation resis”
- The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/ (2005, methodology): “The construction is arguably unusual and so is the construction of Lee and Naor [2006] which is based on the geometry of Heisenberg group.”