  An extended formulation of a polyhedron $P$ is a linear description of a
polyhedron $Q$ together with a linear map $\pi$ such that $\pi(Q)=P$. These
objects are of fundamental importance in polyhedral combinatorics and
optimization theory, and the subject of a number of studies. Yannakakis'
factorization theorem [M. Yannakakis. Expressing combinatorial optimization
problems by linear programs. {\em J. Comput. System Sci.}, 43(3):441--466
(1991)] provides a surprising connection between extended formulations and
communication complexity, showing that the smallest size of an extended
formulation of $P$ equals the nonnegative rank of its slack matrix $S$.
Moreover, Yannakakis also shows that the nonnegative rank of $S$ is at most
$2^c$, where $c$ is the complexity of any \emph{deterministic} protocol
computing $S$. In this paper, we show that the latter result can be
strengthened when we allow protocols to be \emph{randomized}. In particular, we
prove that the base-2 logarithm of the nonnegative rank of any nonnegative
matrix equals the minimum complexity of a randomized communication protocol
computing the matrix in expectation. Using Yannakakis' factorization theorem,
this implies that the base-2 logarithm of the smallest size of an extended
formulation of a polytope $P$ equals the minimum complexity of a randomized
communication protocol computing the slack matrix of $P$ in expectation. We
show that allowing randomization in the protocol can be crucial for obtaining
small extended formulations. Specifically, we prove that for the spanning tree
and perfect matching polytopes, small variance in the protocol forces large
size in the extended formulation.
