We construct an explicit family of total sign matrices whose sign-rank is exponentially larger than their margin complexity. Previously, no superpolynomial separation was known for total matrices. In particular, we give a quantitative answer to a question of Linial, Mendelson, Schechtman, and Shraibman (Combinatorica, 2007), who asked whether the logarithmic dependence on matrix size in the Johnson--Lindenstrauss upper bound for sign-rank is necessary. Our result shows that this dependence on matrix size is nearly tight if the dependence on margin complexity is required to remain polynomial. The construction is the OR of Equality tests on a large enough alphabet. This also exponentially improves sign-rank lower bounds for sparse disjointness and Hamming-distance thresholds.

The proof uses a new one-sided version of Forster's spectral bound for sparse matrices that gives exponentially stronger lower bounds than previous lower bounds. Using the same method, we also obtain direct-sum theorems for unbounded-error communication complexity for OR compositions of expanders and set-membership tests.