Skip to main content
Log in

On the existence of 0/1 polytopes with high semidefinite extension complexity

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

In Rothvoß (Math Program 142(1–2):255–268, 2013) 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^{\varOmega (n)}\) facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high positive semidefinite extension complexity was left open. We answer this question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron projecting to it must be the intersection of a semidefinite cone of dimension \(2^{\varOmega (n)}\) and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26, 193–205 (2001). doi:10.1287/moor.26.2.193.10561

    Article  MATH  MathSciNet  Google Scholar 

  2. Braun, G., Pokutta, S.: Common information and unique disjointness. In: IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pp. 688–697. Berkeley, California (2013)

  3. Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (Beyond Hierarchies). In: 53rd IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 480–489 (2012). ISBN 978-1-4673-4383-1. doi:10.1109/FOCS.2012.10

  4. Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, pp. 161–170. ACM (2013)

  5. Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. In: Mahjoub, A., Markakis, V., Milis, I., Paschos, V. (eds.) Combinatorial Optimization, volume 7422 of Lecture Notes in Computer Science, pp. 129–140. Springer, Berlin (2012). ISBN 978-3-642-32146-7. doi:10.1007/978-3-642-32147-4_13.

  6. Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs semidefinite extended formulations exponential: separation and strong lower bounds. In: Proceedings of STOC (2012a)

  7. Fiorini, S., Rothvoß, T., Tiwary, H.R.: Extended formulations for polygons. Discret. Comput. Geom. 48(3), 658–668 (2012b). ISSN 0179–5376. doi:10.1007/s00454-012-9421-9

  8. Goemans, M.X.: Smallest compact formulation for the permutahedron. Math. Program. 1–7 (2014). doi:10.1007/s10107-014-0757-1

  9. Gouveia, J., Parrilo, P.A., Thomas, R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248–264 (2011)

    Article  MathSciNet  Google Scholar 

  10. Hindry, M., Silverman, J.H.: Diophantine Geometry: An Introduction. Springer, Berlin (2000)

    Book  Google Scholar 

  11. John, F.: Extremum problems with inequalities as subsidiary conditions. In: Studies and Essays Presented to R. Courant on his 60th Birthday, pp. 187–204 (1948)

  12. Katō, T.: Perturbation Theory for Linear Operators. Springer, Berlin (1995)

    MATH  Google Scholar 

  13. Rothvoß, T.: Some 0/1 polytopes need exponential size extended formulations. Math. Program. 142(1–2), 255–268 (2013). doi:10.1007/s10107-012-0574-3

  14. Rothvoß, T.: The Matching Polytope has Exponential Extension Complexity. ArXiv e-prints (2013)

  15. Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 25, 59–98 (1949)

    Article  MathSciNet  Google Scholar 

  16. Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of the STOC 1988, pp. 223–228 (1988)

  17. Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441–466 (1991). doi:10.1016/0022-0000(91)90024-Y

    Article  MATH  MathSciNet  Google Scholar 

  18. Ziegler, G.M.: Lectures on 0/1-Polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes-Combinatorics and Computation, Volume 29 of DMV Seminar, pp. 1–41. Birkhäuser Basel (2000). ISBN 978-3-7643-6351-2. doi:10.1007/978-3-0348-8438-9_1

Download references

Acknowledgments

We are indebted to the anonymous referees for their remarks and the shortening of the proof of Lemma 1.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Sebastian Pokutta.

Additional information

Sebastian Pokutta research reported in this paper was partially supported by NSF grant CMMI-1300144.

Jop Briët was supported by a Rubicon grant from the Netherlands Organisation for Scientific Research (NWO).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Briët, J., Dadush, D. & Pokutta, S. On the existence of 0/1 polytopes with high semidefinite extension complexity. Math. Program. 153, 179–199 (2015). https://doi.org/10.1007/s10107-014-0785-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-014-0785-x

Keywords

Mathematics Subject Classification

Navigation