Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-190 | 17th September 2026 19:19

Efficient Randomized Communication Without Large Monochromatic Rectangles

RSS-Feed




TR26-190
Authors: Haoyu Wang, Pei Wu
Publication: 17th September 2026 20:51
Downloads: 107
Keywords: 


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.



ISSN 1433-8092 | Imprint