17.02.13 - 22.02.13, Seminar 13082

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

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.


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. The minimum size of a Linear Programming formulation equals the nonnegative rank of a certain matrix. In Communication Complexity, one of the biggest open problems is the log-rank conjecture posed by Lovasz and Saks. This can be equivalently stated as saying that the logarithms of the rank and the nonnegative rank are polynomially related for boolean matrices.

Known lower bounds for nonnegative rank are either trivial (rank lower bound) or known not to work in many important cases (nondeterministic communication complexity also known as the biclique covering lower bound).

Over the past couple 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 will bring 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 will be on discussions, open problems and talks surveying the basic tools and techniques from each area. A sampling of the open problems we might discuss can be found at http://www.research.rutgers.edu/~troyjlee/open_problems.pdf