**Feb 17 -- 22 2013.**

Here's the abstract from the proposal.

A number of notorious conjectures and open problems in Matrix Theory, Combinatorial Optimization, and Communication Complexity require proving lower bounds on the nonnegative rank of matrices. In Combinatorial Optimization, one of the most infamous questions is whether the Matching Problem admits a polynomially sized Linear Programming formulation (Schrijver's Book). The minimum size of a Linear Programming formulation equals the nonnegative rank of a certain matrix (Yannakakis 1991). In Communication Complexity, one of the biggest open problems, the log-rank conjecture posed by LovĂˇsz and Saks (1988), involves the question whether the logarithms of the rank and the nonnegative rank are polynomially related for 01-matrices.

The currently known lower bounds for the nonnegative rank are either trivial (rank lower bound) or known not to work in many important cases (biclique covering lower bound). Recently, in Combinatorial Optimization, there has been a surge of interest in lower bounds of sizes of Linear Programming formulations. A number of new methods have been developed and new results have been obtained. Moreover, a new connection linking nonnegative rank directly to a variant of randomized communication complexity has been discovered.

We want to bring together researchers from the fields involved, in order to discuss and perfect the (known and) new techniques, and use (known and) new connections to transfer tools and methods from each one field to the others. We expect that in the wake of this seminar, considerable advances will be made towards resolving some of the questions regarding nonnegative rank.