Lossless Hardness Condensation in Deterministic Communication Complexity

A communication problem can have far more possible inputs than its communication cost would suggest. Must its difficulty already be present on a much smaller set of inputs? We prove that every finite total Boolean matrix of deterministic communication complexity $c\ge 4$ has a submatrix on $2^k$ of its original rows and $2^k$ of its original columns, with $k={\mathrm{\Theta }}_{\epsilon }(c)$ and complexity at least $(1-\epsilon )(k+1)$, for every fixed $0<\epsilon <1$. Since $k+1$ is the maximum possible cost on such a square, the retained problem can be arbitrarily close to maximally hard. This answers affirmatively the lossless condensation question of Hamed Hatami; Göös, Newman, Riazanov, and Sokolov (STOC 2024), who recorded it as Open Problem 2, conjectured a negative answer. Hrubeš previously guaranteed input length $\mathrm{\Omega }(\sqrt{c})$. The same argument gives an original $2^{c-2}$-by-$2^{c-2}$ square retaining at least $c\mathrm{/}3-O(\log c)$ bits of communication complexity. The proof builds on Hrubeš’s counting and covering argument. We count submatrices equipped with short communication protocols: a player names a covering submatrix, then the players run its protocol. This avoids the loss from converting rectangle partitions into protocols. A recursion on rectangles makes the argument constructive. For fixed rational $\epsilon$ and any target depth $d\ge 4$, a deterministic algorithm returns either a protocol of depth below $d$, or a square of original inputs at input length ${\mathrm{\Theta }}_{\epsilon }(d)$ with the same near-maximal guarantee. Its running time is $2^{O(2^d)}$ times a polynomial in the table size. If the original complexity is at least $d$, the algorithm necessarily returns the square. An extension gives constant-factor condensation for any fixed number of number-in-hand players, with bounds independent of the finite output alphabet.