Optimal algorithms and inapproximability results for every CSP?

By Prasad Raghavendra. Symposium on the Theory of Computing, 2008

497 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/0af12c18b1f585b84dba242b77266686e6c23c51

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

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Robust dimension free isoperimetry in Gaussian space (2012, methodology): “This fact has recently found applications in areas such as quantitative social choice and theoretical computer science; see, for example, [14, 22, 24, 25].”
Gaussian Bounds for Noise Correlation of Functions (2007, methodology): “Application to hardness of approximation in computer science were derived in subsequent work in [1] and [26].”
Graph expansion and the unique games conjecture (2010, methodology): “The UGC is shown to imply optimal inapproximability results for classic problems like Max Cut [14], Vertex Cover [15] and Sparsest Cut [16] and constraint satisfaction problems [19].”
Grothendieck's Theorem, past and present (2011, background): “In [136, 137], a (programmatic) approach is proposed to compute KG efficiently.”
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”
The Design of Approximation Algorithms (2011, background): “In fact, due to recent work by Raghavendra [248], we know that the ultimate performance guarantee can surprisingly often be obtained via a semidefinite programming relaxation.”
Complexity Theoretic Limitations on Learning DNF's (2014, background): “They made a strong and general assumption, that says, roughly, that for every random CSP problem, if the number of random constraints is too small to provide short resolution proofs, then the SDP relaxation of [36] has optimal approximation ratio.”
Towards a unified architecture for in-RDBMS analytics (2012, methodology): “The model can be applied to new unlabeled data to make predictions by using a similar SQL query.”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “It is well-known in combinatorial optimization theory that even strong and practical convex relaxations induce lower bounds on the approximation ratio for large classes of problems [37, 47] which makes them inherently sub-optimal.”
Warm-starting quantum optimization (2020, background): “One can, however, encode most problems in combinatorial optimization into a so-called constraint satisfaction problem [74, 97, 98], for which there is an well-known SDP relaxation and a subsequent rounding procedure [74, 97, 98].”
Towards Sharp Inapproximability For Any 2-CSP (2007, unknown): “The main advantage of our results compared to [41] is that [41] requires an actual integrality gap instance in order to be able to derive a hardness result.”