Dagstuhl Workshop "Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices"

As a Valentines day (2012) present, our proposal -- with LeRoy Beasley, Hartmut Klauck, and Troy Lee -- for the organization of a workshop at Dagstuhl Castle has been accepted. Our vision is to bring together people from communication complexity, matrix theory, and combinatorial optimization in the hope of making progress on some of the infamous and long-standing open questions regarding lower bounding the nonnegative rank of matrices, and its applications. The workshop will take place
Feb 17 -- 22   2013.
Dagstuhl hosts a web page for the workshop.
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.