Sign Rank

The sign rank of a matrix with entries in is the least matrix rank of a real matrix having the same entrywise signs as . Equivalently, it is the least for which real vectors satisfy , with all the indicated inner products nonzero (Forster 2002).

For the sign matrix of a two-party Boolean function, the base-2 logarithm of the sign rank agrees, up to an additive constant, with its unbounded-error communication complexity. This model permits any success probability strictly greater than one half, without requiring a fixed positive gap.

Bun and Juvekar (2026) constructed explicit sign matrices with rows and columns and sign rank whose conjunction on two independent input pairs has sign rank . Here denotes big-Theta notation. Consequently, the class of functions with polylogarithmic unbounded-error communication complexity is not closed under intersection.