Cone ranks of nonnegative matrices are new ordered notions of matrix rank with emerging applications in several fields. A well-known example is the nonnegative rank of a nonnegative matrix that appears in areas ranging from communication complexity, to statistics, to combinatorial optimization, and algebraic complexity theory. A related notion arising as an invariant in representations of convex sets as projections of affine slices of the positive semidefinite (psd) cone is the positive semidefinite (psd) rank. The psd rank is a very new quantity and is still relatively poorly understood.

The purpose of this seminar is to bring together researchers from optimization, computer science, real/convex/tropical algebraic geometry, and matrix theory, to discuss relevant techniques from each area that can contribute to the development of both the theory and computation of cone ranks and cone factorizations of nonnegative matrices, as well as their many emerging applications.

We now briefly review the appearance of cone ranks in each of these areas.

In optimization and computer science, a common approach to finding approximate solutions to NP-hard problems is to look at tractable convex relaxations of the problem as either a linear or semidefinite program. An optimal solution to such a relaxation gives a bound on the objective value of the original problem. While much previous work has focused on specific relaxations of a problem, or a family of relaxations coming from a hierarchy, cone ranks allow the study of the best possible linear, semidefinite, or other convex formulations of a NP-hard problem independent of specific construction methods. Linear extended formulations are the best understood so far and an exciting development in this area is the recent breakthrough by Rothvoss showing that the matching polytope does not admit a polynomial sized linear extended formulation, settling a notorious open problem in combinatorial optimization.

In the field of communication complexity, nonnegative and psd ranks are exactly characterized by a model of randomized and quantum communication complexity, respectively. This connection has allowed tools from communication and information theory to help create lower bounds for these ranks.

A central question in the field of real algebraic geometry is the semidefinite representability of convex sets. While polytopes only project to polytopes, affine slices of psd cones have much greater expressive power as their projections are convex sets, which allows the definition of psd rank for semi algebraic convex sets. Psd rank has inherent semi algebraic structure and its study crosses over into real and convex algebraic geometry, algebraic complexity, and semidefinite programming.

• Alexander Barvinok (University of Michigan - Ann Arbor, US) [dblp]
• LeRoy B. Beasley (Utah State University, US) [dblp]
• Greg Blekherman (Georgia Institute of Technology - Atlanta, US) [dblp]
• Daniel Dadush (CWI - Amsterdam, NL) [dblp]
• Ronald de Wolf (CWI - Amsterdam, NL) [dblp]
• Samuel Fiorini (University of Brussels, BE) [dblp]
• Nicolas Gillis (University of Mons, BE) [dblp]
• Francois Glineur (University of Louvain, BE) [dblp]
• João Gouveia (University of Coimbra, PT) [dblp]
• Sebastian Gruler (Universität Konstanz, DE)
• Alexander Guterman (Moscow State University, RU) [dblp]
• Volker Kaibel (Universität Magdeburg, DE) [dblp]
• Hartmut Klauck (Nanyang TU - Singapore, SG) [dblp]
• Kaie Kubjas (Aalto Science Institute, FI) [dblp]
• James R. Lee (University of Washington - Seattle, US) [dblp]
• Troy Lee (National University of Singapore, SG) [dblp]
• Arnau Padrol Sureda (FU Berlin, DE) [dblp]
• Kanstantsin Pashkovich (University of Waterloo, CA) [dblp]
• Teresa Piovesan (CWI - Amsterdam, NL) [dblp]
• Sebastian Pokutta (Georgia Institute of Technology, US) [dblp]
• Raman Sanyal (FU Berlin, DE) [dblp]
• Markus Schweighofer (Universität Konstanz, DE) [dblp]
• Yaroslav Shitov (NRU Higher School of Economics - Moscow, RU) [dblp]
• David Steurer (Cornell University, US) [dblp]
• Jonathan Swenson (University of Washington - Seattle, US)
• Dirk Oliver Theis (University of Tartu, EE) [dblp]
• Rekha R. Thomas (University of Washington - Seattle, US) [dblp]
• Hans Raj Tiwary (Charles University - Prague, CZ) [dblp]
• Antonios Varvitsiotis (National University of Singapore, SG) [dblp]
• Stefan Weltge (Universität Magdeburg, DE) [dblp]