Efficient Randomized Communication Without Large Monochromatic Rectangles

Haoyu Wang, Pei Wu

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^{-\m…