  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\sqrt n$. This
bound is tight up to the constant factor $24$. Finally, we show that there
exists an $n^{o(1)}$-dimensional polytope with at most $n$ vertices and
extension complexity $n^{1-o(1)}$. Our theorems are proved with a range of
different techniques, which we hope will be of further interest.
