{"ID":23664237,"CreatedAt":"2026-09-18T08:14:42.696445972Z","UpdatedAt":"2026-09-18T08:14:42.696445972Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20763","arxiv_id":"2609.20763","title":"Efficient Randomized Communication Without Large Monochromatic Rectangles","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.","short_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 t...","url_abs":"https://arxiv.org/abs/2609.20763","url_pdf":"https://arxiv.org/pdf/2609.20763v1","authors":"[\"Haoyu Wang\",\"Pei Wu\"]","published":"2026-09-17T17:44:11Z","proceeding":"cs.CC","tasks":"[\"cs.CC\"]","methods":"[]","has_code":false}