---
res:
  bibo_abstract:
  - Sometimes, it is possible to represent a complicated polytope as a projection
    of a much simpler polytope. To quantify this phenomenon, the extension complexity
    of a polytope P is defined to be the minimum number of facets of a (possibly higher-dimensional)
    polytope from which P can be obtained as a (linear) projection. This notion is
    motivated by its relevance to combinatorial optimisation, and has been studied
    intensively for various specific polytopes associated with important optimisation
    problems. In this paper we study extension complexity as a parameter of general
    polytopes, more specifically considering various families of low-dimensional polytopes.
    First, we prove that for a fixed dimension d, the extension complexity of a random
    d-dimensional polytope (obtained as the convex hull of random points in a ball
    or on a sphere) is typically on the order of the square root of its number of
    vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie
    on a circle) has extension complexity at most 24√n. This bound is tight up to
    the constant factor 24. Finally, we show that there exists an no(1)-dimensional
    polytope with at most n vertices and extension complexity n1−o(1). Our theorems
    are proved with a range of different techniques, which we hope will be of further
    interest.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Matthew Alan
      foaf_name: Kwan, Matthew Alan
      foaf_surname: Kwan
      foaf_workInfoHomepage: http://www.librecat.org/personId=5fca0887-a1db-11eb-95d1-ca9d5e0453b3
    orcid: 0000-0002-4003-7567
  - foaf_Person:
      foaf_givenName: Lisa
      foaf_name: Sauermann, Lisa
      foaf_surname: Sauermann
  - foaf_Person:
      foaf_givenName: Yufei
      foaf_name: Zhao, Yufei
      foaf_surname: Zhao
  bibo_doi: 10.1090/tran/8614
  bibo_issue: '6'
  bibo_volume: 375
  dct_date: 2022^xs_gYear
  dct_identifier:
  - UT:000798461500001
  dct_isPartOf:
  - http://id.crossref.org/issn/0002-9947
  - http://id.crossref.org/issn/1088-6850
  dct_language: eng
  dct_publisher: American Mathematical Society@
  dct_title: Extension complexity of low-dimensional polytopes@
...