  Generalized probabilistic theories (GPT) provide a general framework that
includes classical and quantum theories. It is described by a cone $C$ and its
dual $C^*$. We show that whether some one-way communication complexity problems
can be solved within a GPT is equivalent to the recently introduced cone
factorisation of the corresponding communication matrix $M$. We also prove an
analogue of Holevo's theorem: when the cone $C$ is contained in
$\mathbb{R}^{n}$, the classical capacity of the channel realised by sending GPT
states and measuring them is bounded by $\log n$.
  Polytopes and optimising functions over polytopes arise in many areas of
discrete mathematics. A conic extension of a polytope is the intersection of a
cone $C$ with an affine subspace whose projection onto the original space
yields the desired polytope. Extensions of polytopes can sometimes be much
simpler geometric objects than the polytope itself. The existence of a conic
extension of a polytope is equivalent to that of a cone factorisation of the
slack matrix of the polytope, on the same cone.
  We show that all $0/1$ polytopes whose vertices can be recognized by a
polynomial size circuit, which includes as a special case the travelling
salesman polytope and many other polytopes from combinatorial optimisation,
have small conic extension complexity when the cone is the completely positive
cone.
  Using recent exponential lower bounds on the linear extension complexity of
polytopes, this provides an exponential gap between the communication
complexity of GPT based on the completely positive cone and classical
communication complexity, and a conjectured exponential gap with quantum
communication complexity.
  Our work thus relates the communication complexity of generalisations of
quantum theory to questions of mainstream interest in the area of combinatorial
optimisation.
