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

Summary

The nonnegative rank is a measure of the complexity of a matrix that has applications ranging from Communication Complexity to Combinatorial Optimization. At the time of the proposal of the seminar, known lower bounds for the nonnegative rank were either trivial (rank lower bound) or known not to work in many important cases (bounding the nondeterministic communication complexity of the support of the matrix).

Over the past couple of years in Combinatorial Optimization, there has been a surge of interest in lower bounds on the sizes of Linear Programming formulations. A number of new methods have been developed, for example characterizing nonnegative rank as a variant of randomized communication complexity. The link between communication complexity and nonnegative rank was also instrumental recently in proving exponential lower bounds on the sizes of extended formulations of the Traveling Salesman polytope, answering a longstanding open problem.

This seminar brought together researchers from Matrix Theory, Combinatorial Optimization, and Communication Complexity to promote the transfer of tools and methods between these fields. The focus of the seminar was on discussions, open problems and talks surveying the basic tools and techniques from each area.

In the short time since the seminar, its participants have made progress on a number of open problems.