On the power of unique 2-prover 1-round games

By Subhash Khot. Proceedings 17th IEEE Annual Conference on Computational Complexity, 2002

1,061 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/abcd4391bed6c66d01eee76e42bb28e8d78f4824

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

On the hardness of approximating minimum vertex cover (2005, methodology): “Following our work, Khot [ Kho02 ] has formulated a specific type of “uniquegames” PCP system that implies such a structural restriction.”
Vertex cover might be hard to approximate to within 2-/spl epsiv/ (2003, background): “Based on a conjecture regarding the power of unique 2prover-1-round games presented in [15], we show that vertex cover is hard to approximate within any constant factor better than 2.”
Robust Optimality of Gaussian Noise Stability (2012, background): “It was essential in [36] for proving the “majority is stablest” conjecture [21, 27], the “it ain’t over until it’s over” conjecture [23], and for establishing the unique games computational hardness [26] of numerous optimization problems including, for example, constraint satisfaction problems [2, 1”
Clustering with qualitative information (2003, background): “Recently, Khot [12] proved the NPhardness of approximating Min-2CNF-deletion within any constant factor based on a conjecture about certain Unique games.”
The Design of Approximation Algorithms (2011, background): “As mentioned previously, the unique games problem and the unique games conjecture was introduced by Khot [192] in the early 2000s.”
The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/ (2005, background): “Subsequent works of Raghavendra and Steurer [2009] and Khot and Saket [2009] cited previously extend this paradigm in two directions: First, their SDP solution satisfies additional constraints given by a super-constant number of rounds of the so-called Sherali-Adams LP hierarchy and, second, they de”
Angular Synchronization by Eigenvectors and Semidefinite Programming (2009, neutral): “Given an instance where 1 − ε fraction of constraints are satisfiable, the Unique Games Conjecture (UGC) of Khot [26] says that it is hard to satisfy even a γ > 0 fraction of the constraints.”
Warm-starting quantum optimization (2020, background): “Conjecture 1 (Unique Games Conjecture [103]).”
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? (2004, methodology): “We also note that it is essential that the (constant) alphabet size M of a Unique Label Instance be a large enough function of η and δ, since [33] gives a polynomial time algorithm that finds a labeling satisfying 1−O(Mη log(1/η)) fraction of edges in the case that 1− η are satisfiable.”
Hardness results for agnostically learning low-degree polynomial threshold functions (2010, background): “[19] S. Khot and R. Saket.”
Gaussian Bounds for Noise Correlation of Functions (2007, background): “xiv, two applications of our results to hardness of approximation in computer science have been established. Both results are in the context of the Unique Games conjecture in computational complexity [17]. Furthermore, both results consider an important problem in computer science, that is - the pro”
Towards Sharp Inapproximability For Any 2-CSP (2007, neutral): “For proving hardness of M AX C UT , Khot et al. [22] made a conjecture called Majority Is Stablest, essentially stating that any boolean function with noise stability signiﬁcantly higher than the majority function must have a variable with high low-degree inﬂuence (and thus in a vague sense be simil”
Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry (2011, positive): “On the other hand, the well-known SDP-based algorithm of Goemans and Williamson [20] achieves an approximation factor of exactly αGW and thus is the optimal algorithm (modulo the Unique Games Conjecture).”
Agnostic Learning of Monomials by Halfspaces Is Hard (2009, result): “D Hardness of Smooth k-Label Cover First we state the bipartite smooth Label Cover given by Khot [31].”
Introduction to Property Testing (2017, methodology): “This tester has played a pivotal role in the PCP constructions of [37] as well as in numerous subsequent PCP constructions including those in [170, 171, 249, 95, 186, 187, 211].”
Optimal algorithms and inapproximability results for every CSP? (2008, methodology): “For the sake of convenience, we shall use the following version of the Unique Games Conjecture[12] which was shown to be equivalent to the original conjecture by [15].”
A Unified Approach to Approximating Partial Covering Problems (2006, methodology): “[18] devised an O(log k)-approximation using the region growing method, a hardness result of (log logn) was given by Chawla, Krauthgamer, Kumar, Rabani and Sivakumar [8], assuming a stronger version of the Unique Games Conjecture [28].”