TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 13082

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

( Feb 17 – Feb 22, 2013 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/13082

Organizers

Contact



Schedule

Motivation

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


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.

Copyright LeRoy B. Beasley, Hartmut Klauck, Troy Lee, and Dirk Oliver Theis

Participants
  • 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]

Related Seminars
  • Dagstuhl Seminar 15082: Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks (2015-02-15 - 2015-02-20) (Details)

Classification
  • data structures / algorithms / complexity
  • optimization / scheduling

Keywords
  • Communication Compleixty
  • Linear & Combinatorial Optimization
  • Matrix Theory