Fetching the paper…
Reading the bibliography…
The groundbreaking work of Rothvo{\ss} [arxiv:1311.2369] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the matching polytope has exponential extension complexity).
Intersection theorems for systems of finite sets
P. Erdős, C. Ko, and R. Rado · 1961
Earlier work this paper cites.
Maximum matching and a polyhedron with 0, 1 vertices
J. Edmonds · 1965
Earlier work this paper cites.
The common information of two dependent random variables
A. Wyner · 1975
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.
On the distributional complexity of disjointness
A. A. Razborov · 1992
Earlier work this paper cites.
Fractional covers and communication complexity
M. Karchmer, E. Kushilevitz, and N. Nisan · 1995
Earlier work this paper cites.
Clique is hard to approximate within 1 − ε 1-\varepsilon
J. Håstad · 1999
Earlier work this paper cites.
An information statistics approach to data stream and communication complexity
Z. Bar-Yossef, T. Jayram, R. Kumar, and D. Sivakumar · 2003
Earlier work this paper cites.
Elements of information theory
T. Cover and J. Thomas · 2006
Earlier work this paper cites.
Approximate formulations for 0-1 knapsack sets
D. Bienstock · 2008
Earlier work this paper cites.
Extended formulations in combinatorial optimization
M. Conforti, G. Cornuéjols, and G. Zambelli · 2010
Cited alongside, same era.
Symmetry matters for the sizes of extended formulations
V. Kaibel, K. Pashkovich, and D. Theis · 2010
Cited alongside, same era.
Extended formulations in combinatorial optimization
V. Kaibel · 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.
From information to exact communication
M. Braverman, A. Garg, D. Pankratov, and O. Weinstein · 2012
Cited alongside, same era.
Common information and unique disjointness
G. Braun and S. Pokutta · 2013
Later among the works it cites.
Information-theoretic approximations of the nonnegative rank
G. Braun, R. Jain, T. Lee, and S. Pokutta · 2013
Later among the works it cites.
On the existence of 0/1 polytopes with high semidefinite extension complexity
J. Briët, D. Dadush, and S. Pokutta · 2013
Later among the works it cites.
Approximate constraint satisfaction requires large LP relaxations
S. O. Chan, J. R. Lee, P. Raghavendra, and D. Steurer · 2013
Later among the works it cites.
Efficient protocols for generating bipartite classical distributions and quantum states
R. Jain, Y. Shi, Z. Wei, and S. Zhang · 2013
Later among the works it cites.
A short proof that the extension complexity of the correlation polytope grows exponentially
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Extended formulations, nonnegative factorizations, and randomized communication protocols
Y. Faenza, S. Fiorini, R. Grappe, and H. R. Tiwary · 2012
Cited alongside, same era.
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
Cited alongside, same era.
Extended Formulations for Combinatorial Polytopes
K. Pashkovich · 2012
Cited alongside, same era.
Some 0/1 polytopes need exponential size extended formulations
T. Rothvoß · 2012
Cited alongside, same era.
On the extension complexity of combinatorial polytopes
D. Avis and H. R. Tiwary · 2013
Cited alongside, same era.
Average case polyhedral complexity of the maximum stable set problem
G. Braun, S. Fiorini, and S. Pokutta
Cited in the paper.
V. Kaibel and S. Weltge · 2013
Later among the works it cites.
S. G. Kolliopoulos and Y. Moysoglou · 2013
Later among the works it cites.
A note on the extension complexity of the knapsack polytope
S. Pokutta and M. Van Vyve · 2013
Later among the works it cites.
Lower bounds on the size of semidefinite programming relaxations
J. Lee, P. Raghavendra, and D. Steurer · 2014
Closest in time.
The matching polytope has exponential extension complexity
T. Rothvoß · 2014
Closest in time.
LP and SDP inapproximability of combinatorial problems
G. Braun, S. Pokutta, and D. Zink · 2015
Closest in time.