A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

M. Yannakakis, Expressing Combinatorial Optimization Problems by Linear Programs, J. Comput. Syst. Sci. 43 (3) (1991) 441–466

1991

Earlier work this paper cites.

A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science 106 (2) (1992) 385–390

1992

Earlier work this paper cites.

R. de Wolf, Nondeterministic quantum query and communication complexities, SIAM J. Comput. 32 (3) (2003) 681–699

2003

Earlier work this paper cites.

E. Kushilevitz, N. Nisan, Communication Complexity, Cambridge University Press, 2006

2006

Earlier work this paper cites.

S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, in: STOC, 2012, pp. 95–106

2012

Cited alongside, same era.

S. Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012

2012

Cited alongside, same era.

D. Avis, H. R. Tiwary, On the Extension Complexity of Combinatorial Polytopes, in: F. V. Fomin, R. Freivalds, M. Z. Kwiatkowska, D. Peleg (Eds.), Automata, Languages, and Programming, Vol. 7965 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2013, pp. 57–68

2013

Cited alongside, same era.

S. Pokutta, M. V. Vyve, A note on the extension complexity of the knapsack polytope, Oper. Res. Lett. 41 (4) (2013) 347–350

2013

Closest in time.

T. Rothvoß, The matching polytope has exponential extension complexity , arXiv:1311.2369 (2013). URL http://arxiv.org/abs/1311.2369

Original

2013

Closest in time.

G. Braun, S. Pokutta, Common information and unique disjointness, in: Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), 2013, pp. 688––697

2013

Closest in time.