Pith. Sign in

REVIEW

Efficient Randomized Communication Without Large Monochromatic Rectangles

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Haoyu Wang, Pei Wu

Computational Complexity · Submitted 17 Sep 2026 · 15 references

Pith's verdict: Resolves a major open problem in communication complexity: BPP not contained in P^NP for total functions, using a clever cheat-sheet + fully linear PCP construction. The paper is rigorous, well-written, and the proof checks out.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 20, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 5 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2609.20763 (version 1)
Pith IDVTEZ6EOX, Pith's permanent record of this paper and its review
CitationHaoyu Wang, Pei Wu. "Efficient Randomized Communication Without Large Monochromatic Rectangles." arXiv:2609.20763 (2026). https://pith.science/paper/VTEZ6EOX
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Total function with efficient randomized protocol has exponentially small monochromatic rectangles, separating BPP from P^{NP}.

The reading

This paper constructs a total Boolean function on n-bit inputs that can be computed by a randomized protocol using only O(log n log log n) bits of communication, yet any monochromatic rectangle (a product region where the function is constant) has density at most $2^{{-n^{Ω(1)}}$}. Such a tiny rectangle density forces any deterministic protocol with adaptive NP queries (the class $P^{{NP}}$ in communication) to have at least polynomial cost. As a result, the paper proves that BPP (randomized efficient communication) is not contained in $P^{{NP}}$ for total Boolean functions, settling an open problem. The construction combines the cheat-sheet framework with fully linear probabilistically checkable proofs.

What carries the argument

The central mechanism is the cheat-sheet construction applied to the Gap-Hamming problem, using a fully linear PCP as the inner verifier. The outer gadget is k Gap-Hamming instances on m-bit strings whose outputs form a k-bit address into a table of m = 2^k certificate entries. The inner gadget is the fully linear PCP of Boneh et al. (2019), which certifies that all Gap-Hamming instances satisfy their promise (each XOR weight is at most m/3 or at least 2m/3). The PCP verifier makes four linear queries to the input and certificate, enabling the randomized protocol to cost O(k log k) bits. The bound on monochromatic rectangles is obtained through a combinatorial argument: any large 0-rectangle would contain a 1-input via the existence of a common certificate share, and 1-inputs themselves are exponentially rare.

Extended reading notes

Core claim

Theorem 1.1 provides, for each n, a total Boolean function F_n satisfying R(F_n) = O(log n log log n) and rect(F_n) ≤ $2^{{-n^{Ω(1)}}$}. The Impagliazzo-Williams product method then implies that any $P^{{NP}}$ protocol for F_n has cost at least $n^{{Ω(1)}}$, establishing BPP ⊄ $P^{{NP}}$ for total functions. A corollary shows $P^{{RP}}$ is strictly contained in BPP, answering a question of Pitassi, Shirley, and Watson. The function is built from k parallel Gap-Hamming instances (each on m-bit strings) whose outputs select a certificate in a table of m = 2^k entries; the selected certificate is checked by a fully linear PCP that uses only four linear queries.

Load-bearing premise

The construction critically relies on the correctness and soundness of the fully linear PCP from Boneh et al. for the specific circuit computing 1 − Ind(z); any flaw in that PCP would invalidate both the randomized protocol and the rectangle bound.

Editorial extensions

If this is right

  • The separation BPP ⊄ P^{NP} for total functions resolves the open question raised by Göös, Pitassi, and Watson (2018).
  • The rectangle density bound shows that the product method of Impagliazzo and Williams yields a tight lower bound up to polynomial factors for this function.
  • The result implies that P^{RP} is strictly weaker than BPP for total functions, as the constructed function lies in BPP but requires P^{RP} cost n^{Ω(1)}.
  • Within the class Σ₂ ∩ Π₂, BPP and P^{NP} are now known to be incomparable for total functions, since NP ⊆ Σ₂∩Π₂ and NP ⊄ BPP was already known.
  • The cheat-sheet plus fully linear PCP template may be adaptable to separate other pairs of communication classes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same construction approach could likely separate randomized from quantum communication for total functions, extending Gavinsky's recent result.
  • The exponential rectangle lower bound suggests that the log-rank conjecture cannot be extended to randomized protocols: here communication is small yet rectangles are tiny.
  • The reliance on the fully linear PCP of Boneh et al. raises the question of whether a similar separation can be proved unconditionally or under weaker cryptographic assumptions.
Original 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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,055 input tokens.

What the abstract itself states, as probabilities: claims first 0.88 · states limitation 0.11 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.05 · states quantitative result 0.98 · compares with prior results 0.71 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 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)})$. result 0.59 0.96 0.89 asserted 1.00
s1 As a corollary, it gives the first total function separation for $\mathrm{BPP}\not\subseteq\mathrm{P}^{\mathrm{NP}}$ in the communication world. interpretation 0.59 0.88 0.23 asserted 1.00
s2 Inspired by Gavinsky's recent work (arXiv:2608.18784), our construction combines the cheat-sheet framework with fully linear PCPs. method 0.97 0.74 0.03 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. Selected communication classes on total functions; new separations are highlighted in red. The second corollary concerns RP, the one-sided-error version of BPP: protocols never err on 0-inputs and have error at most 1/3 on 1-inputs. We have the standard containment P RP ⊆ BPP ∩ P NP . Indeed, error amplification allows efficient adaptive RP-query protocols to be simulated in BPP, while RP ⊆ NP gives the containment in P NP [HH24]. Write P RPcc(F) for the analogous cost with exact RP queries, charged their one-sided randomized communication cost. Since an RP query of cost h ≥ 1 has…
Figure 2. The Gap-Hamming cheat-sheet construction on promised base inputs. The k Gap-Hamming outputs select one of m = 2k entries in the XOR-shared certificate table. The selected certificate is checked against the base input using fully linear PCPs of Boneh et al. [BBCG+19]; the inner predicate tests whether this certificate proves Ind(z) = 1. Excluding large monochromatic rectangles. Ruling out a large 0-rectangle is delicate and involves several steps. Given a somewhat large rectangle, we find a 1-input inside it as follows. First, we retain base inputs on each side that have many…
Figure 3. An adaptive P NP protocol in the model of Göös et al. [GKPW17]. Each box depicts a query on X × Y: the shaded rectangles cover its 1-set, and the white region is its 0-set. A cover by at most 2 h rectangles permits a query of cost h ≥ 1. The exact answer selects the next query; leaves give the final output. Definition 3.1. For a, b ∈ {0, 1} m, the Gap-Hamming function is GapHam(a, b) =    0, |a ⊕ b| ≤ m/3, 1, |a ⊕ b| ≥ 2m/3, ∗, m/3 < |a ⊕ b| < 2m/3. The symbol ∗ means that the output is undefined. Define x = (x1, . . . , xk), y = (y1, . . . , yk), z = (z1, z2, ..., zk) = x ⊕ y,…

Figures reproduced from arXiv:2609.20763 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.