Title :
On the Unique Games Conjecture (Invited Survey)
Author_Institution :
Courant Inst. of Math. Sci., NYU, New York, NY, USA
Abstract :
This article surveys recently discovered connections between the Unique Games Conjecture and computational complexity, algorithms, discrete Fourier analysis, and geometry.
Keywords :
Fourier analysis; computational complexity; game theory; geometry; computational complexity; discrete Fourier analysis; geometry; unique games conjecture; Algorithm design and analysis; Approximation algorithms; Computational complexity; Computational geometry; Engineering profession; Hypercubes; NP-complete problem; Polynomials; Programming profession; User-generated content;
Conference_Titel :
Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
978-1-4244-7214-7
Electronic_ISBN :
1093-0159
DOI :
10.1109/CCC.2010.19
