Fetching the paper…
Reading the bibliography…
In Rothvo\ss{} it was shown that there exists a 0/1 polytope (a polytope whose vertices are in \{0,1\}^{n}) such that any higher-dimensional polytope projecting to it must have 2^{\Omega(n)} facets, i.e., its linear extension complexity is exponential.
Extremum problems with inequalities as subsidiary conditions
F. John · 1948
Earlier work this paper cites.
The synthesis of two-terminal switching circuits
C. E. Shannon · 1949
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs (extended abstract)
M. Yannakakis · 1988
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs
M. Yannakakis · 1991
Earlier work this paper cites.
Perturbation theory for linear operators , volume 132
T. Katō · 1995
Earlier work this paper cites.
Diophantine geometry: an introduction , volume 201
M. Hindry and J. H. Silverman · 2000
Earlier work this paper cites.
Lectures on 0/1-Polytopes
G. M. Ziegler · 2000
Cited alongside, same era.
On polyhedral approximations of the second-order cone
A. Ben-Tal and A. Nemirovski · 2001
Cited alongside, same era.
Smallest compact formulation for the permutahedron
M. X. Goemans · 2009
Cited alongside, same era.
Lifts of convex sets and cone factorizations
J. Gouveia, P. A. Parrilo, and R. Thomas · 2011
Cited alongside, same era.
Approximation Limits of Linear Programs (Beyond Hierarchies)
G. Braun, S. Fiorini, S. Pokutta, and D. Steurer · 2012
Cited alongside, same era.
An information complexity approach to extended formulations
M. Braverman and A. Moitra · 2012
Cited alongside, same era.
Extended formulations for polygons
Extended formulations, nonnegative factorizations, and randomized communication protocols
Y. Faenza, S. Fiorini, R. Grappe, and H. R. Tiwary · 2012
Later among the works it cites.
Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds
S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf · 2012
Later among the works it cites.
Some 0/1 polytopes need exponential size extended formulations
T. Rothvoß · 2012
Later among the works it cites.
Common information and unique disjointness
G. Braun and S. Pokutta · 2013
Closest in time.
The matching polytope has exponential extension complexity
T. Rothvoß · 2013
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
S. Fiorini, T. Rothvoß, and H. R. Tiwary
Cited in the paper.