February 17 – 22 , 2013, Dagstuhl Seminar 13082

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


LeRoy B. Beasley (Utah State University, US)
Hartmut Klauck (Nanyang TU – Singapore, SG)
Troy Lee (National University of Singapore, SG)
Dirk Oliver Theis (University of Tartu, EE)

For support, please contact

Dagstuhl Service Team


Dagstuhl Report, Volume 3, Issue 2 Dagstuhl Report
Aims & Scope
List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]


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.

Summary text license
  Creative Commons BY 3.0 Unported license
  LeRoy B. Beasley, Hartmut Klauck, Troy Lee, and Dirk Oliver Theis

Related Dagstuhl Seminar


  • Data Structures / Algorithms / Complexity
  • Optimization / Scheduling


  • Communication Compleixty
  • Linear & Combinatorial Optimization
  • Matrix Theory


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.