On Covering and Rank Problems for Boolean Matrices and Their Applications

Abstract

We consider combinatorial properties of Boolean matrices and their application to two-party communication complexity. Let A be a binary n x n matrix and let K be a field. Rectangles are sets of entries defined by collections of rows and columns. We denote by rank_B(A) (rank_K(A), resp.) the least size of a family of rectangles whose union (sum, resp.) equals A.

We prove the following:

• - With probability approaching 1, for a random Boolean matrix A the following holds: rank_b≥n(1−o(1)).

• - For finite K and fixed ε>O the following holds: If A is a Boolean matrix with rank _B (A≤t) then there is some matrix $A' \leqslant A$ such that $A - A'$ has at most $\varepsilon \cdot n^2$ non-zero entries and rank _K $\left( {A'} \right) \leqslant t^{O\left( 1 \right)}$.

As applications we mention some improvements of earlier results: (1) With probability approaching 1 a random n-variable Boolean function has nondeterministic communication complexity n, (2) functions with nondeterministic communication complexity l can be approximated by functions with parity communication complexity O(l). The latter complements a result saying that nondeterministic and parity communication protocols cannot efficiently simulate each other. Another consequence is: (3) matrices with small Boolean rank have small matrix rigidity over any field.

Partially supported by DFG grant Me 1077/14-1