Efficient Randomized Communication Without Large Monochromatic Rectangles

In this paper, we construct a total Boolean function with $\tilde{O}(\log n)$ randomized communication protocol, while any monochromatic rectangle has density at most $O(2^{-\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)})$. As a corollary, it gives the first total function separation for $\mathrm{B}\mathrm{P}\mathrm{P}\subseteq ̸{\mathrm{P}}^{\mathrm{N}\mathrm{P}}$ in the communication world. Inspired by Gavinsky’s recent work (arXiv:2608.18784), our construction combines the cheat-sheet framework with fully linear PCPs.