BARC Talk by Pavel Hrubes: Witnessing for non-negative rank and communication complexity

Abstract

If a matrix has rank at least r, it contains a full rank rxr submatrix which witnesses this fact. We discuss whether a similar property holds for related matrix parameters: non-negative rank of a non-negative matrix, and communication complexity of a 0/1 matrix. While exact witnessing is impossible in these cases, a certain approximate version can nevertheless be proved.

Pavel Hrubes is a researcher at the Institute of Mathematics, Czech Academy of Science.