Mon Feb 16 -- Fri Feb 20, 2015
The complete title of the seminar is "Limitations of convex programming: lower bounds on extended formulations and factorization ranks", the official web page is here. As the title suggests, we (myself, Hartmut Klauck, Troy Lee, Rekha Thomas) have conceived it to be more broad than the 2013 workshop, which was mainly on nonnegative rank (and linear extended formulations of combinatorial optimization problems). In the nonnegative rank part (even though new lower bounds on Boolean rank are still very much desired for the relevant matrix families) there will be novelties, too. We plan to invite people from real algebraic geometry, more specifically, algebraic statistics, whose interest is in describing the set of matrices with nonnegative rank at most k as a semialgebraic set.
Just as a teaser, here's my favourite open problem in that area. For positive integers r < n, let f(n,r) be the smallest number q such that the set of all matrices of nonnegative rank at most q is has nonempty relative interior in the set of all rank-r $n\times n$ matrices. Clearly, $k \le f(n,k) \le n$, and Yaroslav Shitov (arXiv:1303.1960) has recently proven that $f(n,3) \le 6n/7$.
Conjecture 1. $f(n,k) = \Omega(n)$ for all k. |
I also like this stronger version.
Conjecture 2. $f(n,k) \sim n$ asymptotically if both k and n tend to infinity. |