Fetching the paper…
Reading the bibliography…
We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric.
The synthesis of two-terminal switching circuits
C. E. Shannon · 1949
Earlier work this paper cites.
Maximization of a linear function of variables subject to linear inequalities
G.B. Dantzig · 1951
Earlier work this paper cites.
A polynomial algorithm in linear programming
L. G. Khachiyan · 1979
Earlier work this paper cites.
On the Shannon capacity of a graph
L. Lovász · 1979
Earlier work this paper cites.
A new polynomial time algorithm for linear programming
N. Karmakar · 1984
Earlier work this paper cites.
Disjunctive programming and a hierarchy of relaxations for discrete optimization problems
E. Balas · 1985
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs (extended abstract)
M. Yannakakis · 1988
Earlier work this paper cites.
The cut polytope and the Boolean quadric polytope
C. De Simone · 1990
Earlier work this paper cites.
A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems
H. D. Sherali and W. P. Adams · 1990
Earlier work this paper cites.
Cones of matrices and set-functions and 0 0 - 1 1 optimization
L. Lovász and A. Schrijver · 1991
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs
M. Yannakakis · 1991
Earlier work this paper cites.
On the distributional complexity of disjointness
A. A. Razborov · 1992
Earlier work this paper cites.
A lift-and-project algorithm for mixed 0-1 programs
E. Balas, S. Ceria, and G. Cornuéjols · 1993
Earlier work this paper cites.
Communication complexity and combinatorial lattice theory
L. Lovász and M. Saks · 1993
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Lectures on Polytopes
G. M. Ziegler · 1995
Earlier work this paper cites.
Convex analysis and minimization algorithms I
C. Lemaréchal and J.B. Hiriart-Urruty · 1996
Earlier work this paper cites.
Introduction to the Theory of Computation
M. Sipser · 1996
Earlier work this paper cites.
Geometry of cuts and metrics
M.M. Deza and M. Laurent · 1997
Earlier work this paper cites.
Communication complexity
E. Kushilevitz and N. Nisan · 1997
Earlier work this paper cites.
Clique is hard to approximate within n 1 − ϵ n^{1-\epsilon}
J. Håstad · 1999
Earlier work this paper cites.
Quantum computation and quantum information
M. A. Nielsen and I. L. Chuang · 2000
Earlier work this paper cites.
Proving integrality gaps without knowing the linear program
S. Arora, B. Bollobás, and L. Lovász · 2002
Earlier work this paper cites.
Quantum communication and complexity
R. de Wolf · 2002
Earlier work this paper cites.
Nondeterministic quantum query and communication complexities
R. de Wolf · 2003
Cited alongside, same era.
Semidefinite programs and combinatorial optimization
L. Lovász · 2003
Cited alongside, same era.
Combinatorial optimization. Polyhedra and efficiency
A. Schrijver · 2003
Cited alongside, same era.
Lattice problems in NP ∩ \cap coNP
D. Aharonov and O. Regev · 2004
Cited alongside, same era.
Exponential lower bound for 2-query locally decodable codes via a quantum argument
I. Kerenidis and R. de Wolf · 2004
Cited alongside, same era.
Lower bounds for local search by quantum arguments
S. Aaronson · 2006
Cited alongside, same era.
Quantum proofs for classical theorems
A. Drucker and R. de Wolf · 2011
Closest in time.
Extended formulations, non-negative factorizations and randomized communication protocols
Y. Faenza, S. Fiorini, R. Grappe, and H. R. Tiwary · 2011
Closest in time.
Combinatorial bounds on nonnegative rank and extended formulations
S. Fiorini, V. Kaibel, K. Pashkovich, and D. O. Theis · 2011
Closest in time.
Lifts of convex sets and cone factorizations
J. Gouveia, P.A. Parrilo, and R. Thomas · 2011
Closest in time.
Extended formulations in combinatorial optimization
V. Kaibel · 2011
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
S. Arora, B. Bollobás, L. Lovász, and I. Tourlakis · 2006
Cited alongside, same era.
Rank bounds and integrality gaps for cutting planes procedures
J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi · 2006
Cited alongside, same era.
Linear programming relaxation of Maxcut
W. Fernandez de la Vega and C. Mathieu · 2007
Cited alongside, same era.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell · 2007
Cited alongside, same era.
Quantum computer science: an introduction
N.D. Mermin · 2007
Cited alongside, same era.
Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut
G. Schoenebeck, L. Trevisan, and M. Tulsiani · 2007
Cited alongside, same era.
An explicit and exponential separation between randomized and quantum correlation complexities, 2011
H. Klauck, T. Lee, and S. Zhang · 2011
Closest in time.
Some 0/1 polytopes need exponential size extended formulations
T. Rothvoß · 2011
Closest in time.
Using extended formulations in practice
L. A. Wolsey · 2011
Closest in time.
Approximation Limits of Linear Programs (Beyond Hierarchies)
G. Braun, S. Fiorini, S. Pokutta, and D. Steurer · 2012
Closest in time.
A counterexample to the Alon-Saks-Seymour conjecture and related problems
H. Huang and B. Sudakov · 2012
Closest in time.
Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix, 2012
T. Lee and D. O. Theis · 2012
Closest in time.
On the extension complexity of combinatorial polytopes
D. Avis and H. R. Tiwary · 2013
Closest in time.
Average case polyhedral complexity of the maximum stable set problem
G. Braun, S. Fiorini, and S. Pokutta · 2013
Closest in time.
Information-theoretic approximations of the nonnegative rank
G. Braun, R. Jain, T. Lee, and S. Pokutta · 2013
Closest in time.
Common information and unique disjointness
G. Braun and S. Pokutta · 2013
Closest in time.
An information complexity approach to extended formulations
M. Braverman and A. Moitra · 2013
Closest in time.
On the existence of 0/1 polytopes with high semidefinite extension complexity, 2013
J. Briët, D. Dadush, and S. Pokutta · 2013
Closest in time.
Approximate constraint satisfaction requires large LP relaxations
S.O. Chan, J.R. Lee, P. Raghavendra, and D. Steurer · 2013
Closest in time.
Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity
H. Fawzi and P.A. Parrilo · 2013
Closest in time.
Generalised probabilistic theories and conic extensions of polytopes, 2013
S. Fiorini, S. Massar, M. K. Patra, and H. R. Tiwary · 2013
Closest in time.
Efficient protocols for generating bipartite classical distributions and quantum states
R. Jain, Y. Shi, Z. Wei, and S. Zhang · 2013
Closest in time.
A short proof that the extension complexity of the correlation polytope grows exponentially, 2013
V. Kaibel and S. Weltge · 2013
Closest in time.
A note on the extension complexity of the knapsack polytope
S. Pokutta and M. Van Vyve · 2013
Closest in time.
The matching polytope has exponential extension complexity
T. Rothvoß · 2013
Closest in time.