  An extended formulation of a polytope P is a polytope Q which can be
projected onto P. Extended formulations of small size (i.e., number of facets)
are of interest, as they allow to model corresponding optimization problems as
linear programs of small sizes.
  The main known lower bounds on the minimum sizes of extended formulations for
fixed polytope P (Yannakakis 1991) are closely related to the concept of
nondeterministic communication complexity. We study the relative power and
limitations of the bounds on several examples.

Combinatorics;Discrete Mathematics