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

• LeRoy B. Beasley (Utah State University, US) [dblp]
• Hamza Fawzi (MIT - Cambridge, US) [dblp]
• Samuel Fiorini (University of Brussels, BE) [dblp]
• Anna Gál (University of Texas - Austin, US) [dblp]
• Nicolas Gillis (UC Louvain-la-Neuve, BE) [dblp]
• Francois Glineur (University of Louvain, BE) [dblp]
• João Gouveia (University of Coimbra, PT) [dblp]
• Alexander Guterman (Moscow State University, RU) [dblp]
• Volker Kaibel (Universität Magdeburg, DE) [dblp]
• Stephen Kirkland (NUI Maynooth, IE) [dblp]
• Hartmut Klauck (Nanyang TU - Singapore, SG) [dblp]
• Raghav Kulkarni (National University of Singapore, SG) [dblp]
• Thomas Laffey (University College Dublin, IE) [dblp]
• Troy Lee (National University of Singapore, SG) [dblp]
• Lek-Heng Lim (University of Chicago, US) [dblp]
• Nathan Linial (The Hebrew University of Jerusalem, IL) [dblp]
• Pablo A. Parrilo (MIT - Cambridge, US) [dblp]
• Kanstantsin Pashkovich (University of Padova, IT) [dblp]
• Sebastian Pokutta (Universität Erlangen-Nürnberg, DE) [dblp]
• Richard Robinson (University of Washington - Seattle, US) [dblp]
• Yaroslav Shitov (NRU Higher School of Economics - Moscow, RU) [dblp]
• Adi Shraibman (Academic College of Tel Aviv, IL) [dblp]
• Dirk Oliver Theis (University of Tartu, EE) [dblp]
• Rekha R. Thomas (University of Washington - Seattle, US) [dblp]
• Hans Raj Tiwary (University of Brussels, BE) [dblp]
• Stefan Weltge (Universität Magdeburg, DE) [dblp]