Explicit Optimal Hardness via Gaussian Stability Results
Abstract
The results of Raghavendra [2008] show that assuming Khot’s Unique Games Conjecture [2002], for every constraint satisfaction problem there exists a generic semidefinite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate exactly the Unique Games hardness of the problem.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2013
- Source ID
- 10.1145/2505766
Entities
People
- Anindya De
- Elchanan Mossel
Organizations
- Division of Computing and Communication Foundations
- National Science Foundation Division of Mathematical Sciences
- Office of Naval Research
- University of California, Berkeley