Fetching the paper…
Reading the bibliography…
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems.
Exponential operators and parameter differentiation in quantum physics
R. M. Wilcox · 1967
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
A. S. Nemirovsky and D. B. Yudin · 1983
Earlier work this paper cites.
An approach to obtaining global extremums in polynomial mathematical programming problems
N. Z. Shor · 1987
Earlier work this paper cites.
The cut polytope and the Boolean quadric polytope
Caterina De Simone · 1989
Earlier work this paper cites.
The Boolean quadric polytope: some characteristics, facets and relatives
Manfred Padberg · 1989
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs
Mihalis Yannakakis · 1991
Earlier work this paper cites.
On the hardness of approximating minimization problems
Carsten Lund and Mihalis Yannakakis · 1993
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X. Goemans and David P. Williamson · 1995
Earlier work this paper cites.
Approximate graph coloring by semidefinite programming
David Karger, Rajeev Motwani, and Madhu Sudan · 1998
Earlier work this paper cites.
Complexity of Null- and Positivstellensatz proofs
Dima Grigoriev and Nicolai Vorobjov · 1999
Earlier work this paper cites.
Global optimization with polynomials and the problem of moments
Jean B. Lasserre · 2000
Earlier work this paper cites.
Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization
Pablo Parrilo · 2000
Earlier work this paper cites.
Complexity of positivstellensatz proofs for the knapsack
Dima Grigoriev · 2001
Earlier work this paper cites.
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Dima Grigoriev · 2001
Earlier work this paper cites.
Approximation algorithms
Vijay V. Vazirani · 2001
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
Subhash Khot · 2002
Earlier work this paper cites.
Mirror descent and nonlinear projected subgradient methods for convex optimization
Amir Beck and Marc Teboulle · 2003
Earlier work this paper cites.
Polylogarithmic inapproximability
Eran Halperin and Robert Krauthgamer · 2003
Cited alongside, same era.
Optimal inapproximability results for max-cut and other 2-variable csps?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2004
Cited alongside, same era.
Asymmetric k k -center is log ∗ n \log^{*}n -hard to approximate
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Joseph Naor · 2005
Cited alongside, same era.
Matrix exponentiated gradient updates for on-line learning and Bregman projection
Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth · 2005
Cited alongside, same era.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Cited alongside, same era.
Optimal algorithms and inapproximability results for every CSP? [extended abstract]
Prasad Raghavendra · 2008
Approximation limits of linear programs (beyond hierarchies)
Gábor Braun, Samuel Fiorini, Sebastian Pokutta, and David Steurer · 2012
Later among the works it cites.
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf · 2012
Later among the works it cites.
Approximability and proof complexity
Ryan O’Donnell and Yuan Zhou · 2012
Later among the works it cites.
Online variance minimization
Manfred K. Warmuth and Dima Kuzmin · 2012
Later among the works it cites.
On the existence of 0/1 polytopes with high semidefinite extension complexity
Jop Briët, Daniel Dadush, and Sebastian Pokutta · 2013
Later among the works it cites.
Approximate constraint satisfaction requires large LP relaxations
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Linear level Lasserre lower bounds for certain k-CSPs
G. Schoenebeck · 2008
Cited alongside, same era.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2009
Cited alongside, same era.
Integrality gaps for Sherali-Adams relaxations
M. Charikar, K. Makarychev, and Y. Makarychev · 2009
Cited alongside, same era.
Sums of squares, moment matrices and optimization over polynomials
Monique Laurent · 2009
Cited alongside, same era.
CSP gaps and reductions in the lasserre hierarchy
Madhur Tulsiani · 2009
Cited alongside, same era.
Towards sharp inapproximability for any 2-CSP
Per Austrin · 2010
Cited alongside, same era.
Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer · 2013
Later among the works it cites.
Equivariant semidefinite lifts and sum-of-squares hierarchies
H. Fawzi, J. Saunderson, and P. A. Parrilo · 2013
Later among the works it cites.
Some 0/1 polytopes need exponential size extended formulations
Thomas Rothvoß · 2013
Later among the works it cites.
Quantum information theory
Mark M. Wilde · 2013
Later among the works it cites.
Rounding sum-of-squares relaxations
Boaz Barak, Jonathan A. Kelner, and David Steurer · 2014
Closest in time.
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak and David Steurer · 2014
Closest in time.
Theory of convex optimization for machine learning
S. Bubeck · 2014
Closest in time.
Hamza Fawzi, João Gouveia, Pablo A. Parrilo, Richard Z. Robinson, and Rekha R. Thomas · 2014
Closest in time.
On the power of symmetric LP and SDP relaxations
James R. Lee, Prasad Raghavendra, David Steurer, and Ning Tan · 2014
Closest in time.
Analysis of Boolean Functions
Ryan O’Donnell · 2014
Closest in time.
The matching polytope has exponential extension complexity
Thomas Rothvoß · 2014
Closest in time.