Communication protocol achieves efficiency without large simple patterns
Efficient Randomized Communication Without Large Monochromatic Rectangles
Computational Complexity
Summary
This paper studies a way for two computers to talk and solve problems together efficiently using randomness. The authors show it's possible to have a fast communication method even when the usual simple building blocks, called monochromatic rectangles, are extremely rare. Their example breaks previous assumptions in the field, showing a surprising gap between two kinds of problem-solving power in communication complexity. They build on recent ideas combining cheat-sheet techniques and special proof systems called fully linear PCPs.
What this means in practice
- •For distributed system designers: Develop communication protocols that use minimal communication bits even when simple partitions of input space are unavailable.
- •For cryptography engineers: Inform designs of protocols where proving correctness with limited communication is critical despite complex input structures.
A theory result. No direct application yet.
Authors
Haoyu Wang, Pei Wu
Abstract
In this paper, we construct a total Boolean function with $\widetilde{O}(\log n)$ randomized communication protocol, while any monochromatic rectangle has density at most $O(2^{-\mathrm{poly}(n)})$. As a corollary, it gives the first total function separation for $\mathrm{BPP}\not\subseteq\mathrm{P}^{\mathrm{NP}}$ in the communication world. Inspired by Gavinsky's recent work (arXiv:2608.18784), our construction combines the cheat-sheet framework with fully linear PCPs.