Pith. sign in

REVIEW 3 major objections 8 minor 57 references

Gap-Majority: The Third Composition Gadget for Communication

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.

T0 review reviewed 2026-07-09 challenge →

load-bearing objection Gap-majority composition theorem for information cost is new and correct; the numerical concern in Appendix A is overstated. the 3 major comments →

arxiv 2607.07396 v1 pith:LZVPOBDG submitted 2026-07-08 cs.CC cs.DS

Gap-Majority Lemmas in Communication Complexity

Pachara Sawettamalya , Huacheng Yu This is my paper
classification cs.CC cs.DS
keywords gap-majoritycommunicationgapmajinformationldotslemmamathsfbits
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that in two-player communication, computing the gap-majority composition GapMAJ∘f^n — which asks whether the sum of n copies of a function f exceeds +0.01√n or falls below -0.01√n — requires n times the information cost of computing a single instance of f, up to a constant additive loss. The result is asymptotically optimal in both the linear scaling of information cost and the constant-to-constant error tradeoff (from 0.501 success on f to 0.99 success on the composition). This makes GapMAJ only the third explicit outer gadget, after identity and XOR, to admit a strong composition theorem in the two-player communication setting. The proof combines two ingredients: a variance bound showing that any protocol for GapMAJ∘f^n forces the observer's variance of f^{+n} below 0.99n, and a new direct-sum theorem that simultaneously decomposes both information cost and observer's variance across n coordinates with only constant additive loss. A round-preserving variant achieves O(log n) additive loss instead of O(1), maintaining the same number of communication rounds.

Core claim

The central technical contribution is a direct-sum theorem for the simultaneous decomposition of information cost and observer's variance (Lemma 3.3). The observer's variance, defined as the expected conditional variance of f(X,Y) given the protocol transcript and public randomness, serves as the bridge between gap-majority computation and single-instance hardness. The proof works by recursively decomposing an n-coordinate protocol into two n/2-coordinate subprotocols via a protocol decomposition technique that embeds real inputs into simulated larger inputs, then tracks how both information and variance distribute across coordinates. Rounding the auxiliary messages Z_0 and Z_1 (conditional-

What carries the argument

Observer's variance: the expected variance of f(X,Y) as seen by an external observer who knows the transcript and public randomness but not the private inputs. It serves as the quantitative bridge between gap-majority success probability and single-instance information cost.

Load-bearing premise

The variance bound (Lemma 3.2), which establishes that any gap-majority protocol forces observer's variance below 0.99n, relies on numerical calculations of specific binomial-sum approximations and constants (0.486, 0.014, 0.6724) that were verified with AI assistance. If any of these numerical bounds are incorrect, the variance bound fails and the main theorem's proof does not go through.

What would settle it

Construct a base function f and a protocol for GapMAJ∘f^n that achieves 0.99 success with information cost o(n) times the information complexity of f at 0.501 success, which would contradict the linear scaling claim.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Provides a generic black-box tool to lift any decision-problem lower bound to an approximation-problem lower bound, following a two-step recipe: reduce the target approximation problem to approximating f^{+n}, then apply the gap-majority lemma to a known lower bound for f.
  • Recovers the optimal Ω(n) communication lower bound for Gap-Hamming via a clean reduction from set-disjointness, offering a conceptually simpler proof than prior approaches.
  • Derives a tight Ω(min{m, mn/(ε²T)}) single-pass streaming lower bound for (1±ε)-approximate triangle counting, improving prior bounds by the missing 1/ε² factor.
  • The round-preserving variant (Theorem 1.4) enables one-way communication lower bounds, which is essential for streaming reductions where the round restriction is the primary source of hardness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The gap-majority lemma could potentially serve as a unifying framework for other gap-type lower bounds in communication complexity, such as gap-orthogonality or frequency-moment estimation, wherever a decision problem can be identified whose n-fold sum naturally embeds into the target approximation task.
  • The direct-sum theorem for simultaneous information-and-variance decomposition (Lemma 3.3) may have independent utility beyond gap-majority, for instance in proving lower bounds for composed functions where both information revelation and output uncertainty must be controlled simultaneously.
  • The open question of achieving O(1) information loss with round preservation (the conjectured best-of-both-worlds) suggests a potential gap between the information-theoretic structure of the problem and the round constraints, which if resolved would strengthen streaming lower bounds that rely on one-way reductions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 8 minor

Summary. This paper proves an information-theoretically optimal gap-majority lemma for two-party randomized communication. The main result (Theorem 1.3) shows that computing GapMAJ_n ∘ f^n with success probability 0.99 requires n·(I - O(1)) bits of information, where I is the information cost of computing f with success probability 0.501. A round-preserving variant (Theorem 1.4) is also proved. The proof combines two ingredients: (1) a variance bound (Lemma 3.2) showing that any protocol computing gap-majority has low observer's variance, adapted from [BGW20], and (2) a new direct-sum theorem (Lemma 3.3) decomposing information cost and observer's variance simultaneously via a protocol decomposition technique. Applications to Gap-Hamming and streaming triangle counting are given.

Significance. The paper identifies GapMAJ as the third explicit outer gadget with a strong composition theorem in two-player communication, after identity and XOR. The direct-sum theorem for variance and information (Lemma 3.3) is a genuine technical contribution: the decomposition simultaneously tracks both information cost and observer's variance, and the recursive argument in Section 4 is clean. The round-preserving variant (Lemma 3.6) handles the additional constraint that Bob cannot relay his answer back to Alice, requiring a modified decomposition. The triangle counting lower bound improves the prior bound of [BOV13] by a 1/ε² factor, which is a concrete quantitative improvement. The constants in the main theorem (gap 0.01, success 0.99, base success 0.501) are explicit and the result is falsifiable.

major comments (3)
  1. Appendix A, proof of Lemma 3.2: The numerical constant 0.6724 appears to be incorrect by a factor of 2. Tracing the arithmetic: the sum is evaluated via Fact A.1 as 2^n · sqrt(n/(2π)) · [2φ(0.005) - φ(1.162) - φ(1.098) - φ(0)], where φ(c) = e^{-2c²}. Numerically, 2(0.99995) - 0.0671 - 0.0897 - 1 = 0.8431, and sqrt(1/(2π)) ≈ 0.3989, giving a coefficient of approximately 0.336, not 0.6724. However, this error is harmless for the downstream conclusion: the bound Φ_obs ≤ 0.99n only requires the constant c in (c√n)² ≥ 0.01n, i.e., c ≥ 0.1. The corrected constant 0.336 still yields Φ_obs ≤ (1 - 0.113)n = 0.887n ≤ 0.99n, leaving a safety margin of roughly 3.4×. The authors should correct the constant (and re-verify the numerical bounds) in revision, but this does not affect the validity of Lemma 3.2 or the main theorem.
  2. Section 3.1, proof of Theorem 1.3: The chain of inequalities from Φ_obs(η@f) ≤ 0.998 to success ≥ 0.501 uses the bound 4p(1-p) ≥ 2p for p ∈ [0, 1/2]. This is correct (since 4p(1-p) ≥ 2p iff p ≤ 1/2). However, the step from Φ_obs ≤ 0.99n (Lemma 3.2) to Φ_obs(η@f) ≤ 0.998 (via Lemma 3.3 with Δ = 0.008) yields 0.99 + 0.008 = 0.998, and then the error bound gives p ≤ 0.499, i.e., success ≥ 0.501. The margin is tight: 0.998 is just barely below 1. The authors should verify that the additive losses in Lemma 3.3 (the Δ/16 per decomposition step, summed over log n levels to give nΔ) are correctly accounted for. With Δ = 0.008, the total variance loss is n·0.008, giving per-coordinate variance 0.99 + 0.008 = 0.998. This checks out, but the tightness means any unaccounted loss in Lemma 3.2 (e.g., from the numerical constant issue above) could be consequential. Given the safety margin identified in
  3. Section 5, proof of Lemma 3.6: The recursive decomposition peels off one coordinate at a time (π into π_n and π_{<n}, then π_{<n} into π_{n-1} and π_{<n-1}, etc.), yielding n protocols. The information cost accumulation gives Σ IC(π_i) ≤ IC(π) + O(|A| · n · log(n/Δ)), so the average protocol has IC(η) ≤ IC(π)/n + O(|A| · log(n/Δ)). With |A| = 2 (for GapMAJ), this gives O(log n) additive loss, matching Theorem 1.4. This is correct. However, the variance accumulation in Lemma 5.3 gives additive loss Δ/32 per step (not Δ/16 as in the balanced decomposition of Lemma 4.4), and there are n-1 steps, so the total is n·Δ/32. The proof of Lemma 3.6 states the bound as nΔ/16. Please reconcile: is the per-step loss Δ/32 (as stated in Lemma 5.3) or Δ/16 (as used in the proof of Lemma 3.6)? This is a factor-of-2 discrepancy in the additive constant, which does not affect the asymptotic statement but应该
minor comments (8)
  1. The abstract states f: X → {±1} but the main theorem (Theorem 1.3) uses f: X × Y → {±1}. The abstract should reflect the two-party setting.
  2. Section 1.1, footnote 2: the informal argument for why η must reveal Ω(1) bits could be stated more precisely.
  3. Lemma 3.5 is stated without proof (deferred as an analog of Lemma 3.2). Given that Lemma 3.2's proof has the numerical issue above, the authors should at least sketch why the bounded-round version goes through identically.
  4. Claim 5.1 is stated without proof. While the authors note it is analogous to Claim 4.1, the round-preserving setting has structural differences (the Z_n message is appended to M_r rather than sent separately), so a brief verification would help.
  5. Section 6.2: the parameter setup (t = Θ(1/ε²), k = Θ(√(mn/τ)), b = Θ(ε²τ/n)) should specify the leading constants more explicitly, as the proof of Claim 6.10 relies on O(1/ε) ≤ 0.01√t, which requires t ≥ 10⁴/ε².
  6. The AI Disclosure states that numerical calculations in Appendix A were assisted by ChatGPT. The factor-of-2 error in the constant 0.6724 likely originates from this. The authors should independently verify all numerical bounds in Appendix A.
  7. Fact A.1: the formula gives sqrt(n/(8π)) but the proof uses sqrt(n/(2π)). Please reconcile.
  8. Equation (10): the bound |{z : ⟨z,1_n⟩ ≥ 0.01√n}| ≥ 0.496 · 2^n should be justified (it follows from standard binomial tail bounds but is stated without citation).

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful and constructive report. All three major comments identify genuine errors in numerical constants or proof arithmetic; we correct all of them in revision. None of the corrections affects the validity of the main theorems (Theorem 1.3, Theorem 1.4) or the applications, as the referee themselves notes. We address each point below.

read point-by-point responses

  1. Referee: Appendix A, proof of Lemma 3.2: The numerical constant 0.6724 appears to be incorrect by a factor of 2. The corrected constant is approximately 0.336, but this does not affect the downstream conclusion.

    Authors: The referee is correct. We have re-derived the calculation. The expression evaluates to 2^n · sqrt(n/(2π)) · [2φ(0.005) − φ(1.162) − φ(1.098) − φ(0)], where φ(c) = e^{−2c²}. Numerically, 2(0.99995) − 0.0671 − 0.0897 − 1 = 0.8431, and sqrt(1/(2π)) ≈ 0.3989, giving a coefficient of approximately 0.336, not 0.6724. The factor-of-2 error arose from an incorrect transcription of the numerical computation (which was assisted by ChatGPT, as noted in the AI Disclosure). We will correct the constant to 0.336 throughout Appendix A. As the referee observes, this does not affect Lemma 3.2: the corrected bound gives Φ_obs(π@f^{+n}) ≤ n − (0.336√n)² = n − 0.113n = 0.887n ≤ 0.99n, with a safety margin of roughly 3.4×. We will also re-verify all other numerical bounds in Appendix A to ensure no further transcription errors exist. revision: yes

  2. Referee: Section 3.1, proof of Theorem 1.3: Verify that the additive losses in Lemma 3.3 are correctly accounted for, given the tight margin (0.998 is barely below 1).

    Authors: We have carefully re-verified the chain of inequalities. The accounting is as follows: Lemma 3.2 gives Φ_obs(π@f^{+n}) ≤ 0.99n. Lemma 3.3 with Δ = 0.008 gives Φ_obs(η@f) ≤ 0.99 + 0.008 = 0.998. The recursive decomposition in the proof of Lemma 3.3 incurs a total variance loss of Σ_{ℓ=1}^{log₂ n} 2^{ℓ−1} · Δ/16 = (n−1)·Δ/16 ≤ nΔ, so the per-protocol bound is Φ_obs(π@f^{+n})/n + Δ = 0.99 + 0.008 = 0.998. Then 4p(1−p) ≥ 2p for p ∈ [0, 1/2] yields error ≤ 0.499, i.e., success ≥ 0.501. This checks out. Moreover, the referee's concern about the tightness of the margin is fully addressed by the correction in Comment 1: with the corrected constant 0.336, Lemma 3.2 actually gives Φ_obs(π@f^{+n}) ≤ 0.887n, so the chain becomes 0.887 + 0.008 = 0.895, which is far from 1. The margin was only tight because of the erroneous constant 0.6724; after correction, there is ample room. We will add a remark noting this safety margin explicitly. revision: yes

  3. Referee: Section 5, proof of Lemma 3.6: Reconcile the per-step variance loss Δ/32 (Lemma 5.3) with the nΔ/16 used in the proof of Lemma 3.6.

    Authors: The referee is correct that there is a factor-of-2 discrepancy. Lemma 5.3 states a per-step additive loss of Δ/32 in variance. The recursive decomposition in the proof of Lemma 3.6 performs n−1 such steps, so the total variance loss should be (n−1)·Δ/32, which we should write as nΔ/32 (or more precisely (n−1)Δ/32). The proof of Lemma 3.6 incorrectly writes nΔ/16, which appears to be a carryover from the balanced decomposition in Section 4 (where the per-step loss is indeed Δ/16). This is a typo in the proof body. The statement of Lemma 3.6 itself (with additive loss +Δ in the variance bound) remains correct, since (n−1)Δ/32 < nΔ, so the per-protocol bound is at most Φ_obs(π@f^{+n})/n + Δ. We will correct the proof to read nΔ/32 in place of nΔ/16. We will also add a brief note clarifying the difference in per-step loss between the balanced decomposition (Δ/16, Section 4) and the sequential decomposition (Δ/32, Section 5), which arises because in the round-preserving case, only π_{<n} incurs the rounding loss while π_n does not. revision: yes

Circularity Check

0 steps flagged

No circularity: main theorem derives from independently proved Lemma 3.3 and externally adapted Lemma 3.2

full rationale

The paper's main result (Theorem 1.3) is assembled from two ingredients: Lemma 3.2 (gap-majority implies low variance, adapted from [BGW20], an external FOCS 2020 paper by Braverman-Garg-Woodruff) and Lemma 3.3 (a new direct-sum theorem for variance and information, proved from first principles in Section 4 using the rectangle property and standard information-theoretic identities). Neither ingredient is defined in terms of the conclusion. Lemma 3.2's proof in Appendix A uses Fact A.1 (a binomial sum approximation) and numerical constants to bound the observer's variance; while the skeptic flags a possible factor-of-2 discrepancy in the constant 0.6724, this is a correctness concern (the bound still holds with corrected arithmetic), not a circularity issue—the inputs (binomial sums, success probability 0.99) are not defined in terms of the output (variance ≤ 0.99n). Lemma 3.3's proof constructs protocols via recursive decomposition (Figures 1-2) and proves the information/variance decomposition via Claims 4.1-4.3 using the rectangle property (Proposition 2.2, cited from [Yu22]) and Fact 2.1 (Cauchy-Schwarz). The self-citation [SY25] is for the XOR lemma, a different result, and the decomposition technique from [Yu22; SY25] is a methodological tool, not a load-bearing premise that assumes the target theorem. The lower bound applications (Section 6) reduce to external problems (set-disjointness, indexing) with known lower bounds (Theorems 6.2, 6.4). No step reduces to its inputs by construction.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 2 invented entities

The axiom ledger is minimal. The paper introduces two new mathematical measures (observer's and Bob's variance) but no new physical entities or ad hoc postulates. The free parameters are problem-definition constants, not fitted values. The key axioms are standard probability/communication complexity tools. The main concern is the numerical verification of constants in Lemma 3.2, which is an empirical/computational issue rather than an axiom issue.

free parameters (4)
  • Gap constant 0.01 = 0.01
    The gap threshold 0.01√n in GapMAJ is a fixed constant chosen for the problem definition. It is not fitted to data but is a problem parameter.
  • Success probability 0.99 = 0.99
    The success probability for the gap-majority protocol. Chosen as a high constant; the theorem shows this trades off optimally with 0.501 for the base function.
  • Base success probability 0.501 = 0.501
    The success probability for computing f in the base case. Chosen as a bare majority; the theorem shows this trades off optimally with 0.99 for the composition.
  • Variance parameter Δ = 0.008
    The additive loss parameter in Lemma 3.3, set to 0.008 in the proof of Theorem 1.3 so that the final variance bound 0.998 yields error ≤ 0.499.
axioms (5)
  • standard math Rectangle property (Proposition 2.2): In a communication protocol over product distributions, conditioned on the transcript and randomness, disjoint coordinate blocks are independent.
    Standard property of communication protocols, cited from [Yu22] Section 3.4. Used in Claims 4.1, 4.3, 5.2.
  • standard math Fact 2.1 (Cauchy-Schwarz): E_B[Var_A[f(A)|B]] ≤ Var_A[f(A)].
    Standard probability fact used in the variance decomposition proofs.
  • standard math Fact A.1: Binomial sum approximation P_{i=0}^{c√n} C(n,n/2+i)·i = 2^n·√(n/8π)·(1-φ(c)) + o(2^n√n) where φ(c)=e^{-2c²}.
    Standard normal approximation to binomial sums, used in the proof of Lemma 3.2.
  • domain assumption Information cost decomposition: The information cost of a protocol decomposes additively across coordinate blocks up to the cost of communicating auxiliary variables.
    This is the core of the decomposition technique, used in Claims 4.1 and 5.1. It follows from the chain rule for mutual information and the rectangle property.
  • domain assumption E_μ[f(x,y)]=0 (balanced distribution)
    Required for Lemma 3.2 and Theorems 1.3, 1.4. The zero-mean condition ensures the gap-majority problem is well-defined (both cases have significant probability). Not required for Lemma 3.3.
invented entities (2)
  • Observer's variance Φ_obs(π@f) independent evidence
    purpose: Measures the expected variance of f(X,Y) from an external observer's perspective after the protocol concludes, i.e., conditioned on the transcript and public randomness.
    This is a new information-theoretic measure introduced by the paper. It is not a new physical entity but a mathematical tool. It has independent falsifiable content: if the gap-majority protocol succeeds with probability 0.99, then Φ_obs must be ≤ 0.99n (Lemma 3.2), which is a testable prediction.
  • Bob's variance Φ_Bob(π@f) independent evidence
    purpose: Measures the expected variance of f(X,Y) from Bob's perspective at the end of a bounded-round protocol, conditioned on the transcript, randomness, answer, and Bob's input.
    Introduced for the round-preserving variant. Like observer's variance, it is a mathematical measure with a clear operational interpretation related to distributional error.

reviewed 2026-07-09 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Gap-Majority Lemmas in Communication Complexity." pith.science (2026). https://pith.science/paper/LZVPOBDG

@misc{pith2026260707396,
  author       = {Pith},
  title        = {Pith review of: Gap-Majority Lemmas in Communication Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LZVPOBDG}},
  note         = {Machine review of arXiv:2607.07396}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We prove an information-theoretically optimal \emph{gap-majority lemma} in the two-player randomized communication model. For a base function $f: \mathcal{X} \to \{\pm 1\}$, its $n$-fold \emph{gap-majority composition}, denoted $\mathsf{GapMAJ} \circ f^n$, takes $n$ inputs $(X_1, \ldots, X_n)$ and distinguishes whether $f^{+n}(X_1,\ldots,X_n) := f(X_1) + \ldots + f(X_n)$ is at least $0.01\sqrt{n}$ or at most $-0.01\sqrt{n}$. We show that if computing $f$ with success probability $0.501$ requires $I$ bits of information, then computing $\mathsf{GapMAJ} \circ f^n$ with success probability $0.99$ requires $n \cdot (I - O(1))$ bits of information. This result is asymptotically optimal in two aspects: it achieves the correct linear scaling of information cost and the correct constant-constant tradeoff between error rates. This makes $\mathsf{GapMAJ}$, to our knowledge, only the third explicit outer gadget that admits a strong composition theorem in the two-player communication setting, following the identity and XOR gadgets. From an application side, our gap-majority lemma can be viewed as a generic amplification tool that lifts the hardness of deciding $f$ into the hardness of approximating $f^{+n}$. Using this framework, we give a new proof to the communication lower bound of Gap-Hamming and derive a tight streaming lower bound of triangle counting, demonstrating the versatility of the gap-majority lemma.

Figures

Figures reproduced from arXiv: 2607.07396 by Huacheng Yu, Pachara Sawettamalya.

Figure 1
Figure 1. Figure 1: The protocol π0 resulting from decomposing π. 9 [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The protocol π1 resulting from decomposing π. Equivalently, we may adopt the following distributional view of each protocol. Note that we write (M, Zi) to denote a transcript M followed by an extra message Zi . • π0 = (X0, Y0,(M, Z0), RY1) where Z0 = E Y0 [f +(X0, Y0) | MRX0Y1] computable by Alice. This is because Z0 is a deterministic function of MRX0Y1 in which she knows by the end of π. • π1 = (X1, Y1,(… view at source ↗
Figure 3
Figure 3. Figure 3: The protocol π <n resulting from decomposing π A protocol π n over the input distribution (X′ , Y ′ ) ∼ µ 1. Alice pretends that her input consists of n coordinates, and writes it as X = (X1, . . . , Xn). 2. Bob pretends that his input consists of n coordinates, and writes it as Y = (Y1, . . . , Yn). 3. Alice embeds X′ into Xn, and Bob embeds Y ′ into Yn. 4. Players use public randomness to jointly draw X<… view at source ↗
Figure 4
Figure 4. Figure 4: The protocol π n resulting from decomposing π. Equivalently, we may adopt the following distributional view of each protocol. • π n = (Xn, Yn, M, A, RX<n). • π <n = (X<n, Y<n, M⊙Zn, A, RYn) where Zn consists of Z a n = E Y<n [f +(X<n, Y<n) | MRX<nYn, A = a] for each a ∈ A computable solely by Alice. Here we write M ⊙ Zn to denote the r-round transcript M with Alice appending Zn to her last message Mr. Note… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

57 extracted references · 57 canonical work pages · 2 internal anchors

  1. [1]

    57th Annual

    Pachara Sawettamalya and Huacheng Yu , title =. 57th Annual. 2025 , url =. doi:10.1145/3717823.3718258 , timestamp =

    work page doi:10.1145/3717823.3718258 2025

  2. [2]

    Huacheng Yu , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00114 , timestamp =

    work page doi:10.1109/focs54457.2022.00114 2022

  3. [3]

    Roberson , editor =

    Mark Braverman and Sumegha Garg and David P. Woodruff , title =. 61st. 2020 , url =. doi:10.1109/FOCS46700.2020.00038 , timestamp =

    work page doi:10.1109/focs46700.2020.00038 2020

  4. [4]

    2015 , url =

    Mark Braverman , title =. 2015 , url =. doi:10.1137/130938517 , timestamp =

    work page doi:10.1137/130938517 2015

  5. [5]

    An information statistics approach to data stream and communication complexity , journal =

    Ziv Bar. An information statistics approach to data stream and communication complexity , journal =. 2004 , url =. doi:10.1016/J.JCSS.2003.11.006 , timestamp =

    work page doi:10.1016/j.jcss.2003.11.006 2004

  6. [6]

    Boaz Barak and Mark Braverman and Xi Chen and Anup Rao , title =. 42nd. 2010 , url =. doi:10.1145/1806689.1806701 , timestamp =

    work page doi:10.1145/1806689.1806701 2010

  7. [7]

    Siddharth Iyer and Anup Rao , title =. 65th. 2024 , url =. doi:10.1109/FOCS61266.2024.00034 , timestamp =

    work page doi:10.1109/focs61266.2024.00034 2024

  8. [8]

    56th Annual

    Siddharth Iyer and Anup Rao , title =. 56th Annual. 2024 , url =. doi:10.1145/3618260.3649726 , timestamp =

    work page doi:10.1145/3618260.3649726 2024

  9. [9]

    54th Annual

    Mark Braverman and Anup Rao and Omri Weinstein and Amir Yehudayoff , title =. 54th Annual. 2013 , url =. doi:10.1109/FOCS.2013.85 , timestamp =

    work page doi:10.1109/focs.2013.85 2013

  10. [10]

    A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity , booktitle =

    Rahul Jain and Attila Pereszl. A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity , booktitle =. 2012 , url =. doi:10.1109/FOCS.2012.42 , timestamp =

    work page doi:10.1109/focs.2012.42 2012

  11. [11]

    2011 , url =

    Mark Braverman and Anup Rao , title =. 2011 , url =. doi:10.1109/FOCS.2011.86 , timestamp =

    work page doi:10.1109/focs.2011.86 2011

  12. [12]

    Theory and Applications of Trapdoor Functions (Extended Abstract) , booktitle =

    Andrew Chi. Theory and Applications of Trapdoor Functions (Extended Abstract) , booktitle =. 1982 , url =. doi:10.1109/SFCS.1982.45 , timestamp =

    work page doi:10.1109/sfcs.1982.45 1982

  13. [13]

    Levin , title =

    Leonid A. Levin , title =. Comb. , volume =. 1987 , url =. doi:10.1007/BF02579323 , timestamp =

    work page doi:10.1007/bf02579323 1987

  14. [14]

    Russell Impagliazzo and Avi Wigderson , title =. 29th. 1997 , url =. doi:10.1145/258533.258590 , timestamp =

    work page doi:10.1145/258533.258590 1997

  15. [15]

    36th Annual Symposium on Foundations of Computer Science , pages =

    Russell Impagliazzo , title =. 36th Annual Symposium on Foundations of Computer Science , pages =. 1995 , url =. doi:10.1109/SFCS.1995.492584 , timestamp =

    work page doi:10.1109/sfcs.1995.492584 1995

  16. [16]

    Andrew Drucker , title =. Comput. Complex. , volume =. 2012 , url =. doi:10.1007/S00037-012-0043-7 , timestamp =

    work page doi:10.1007/s00037-012-0043-7 2012

  17. [17]

    A Strong XOR Lemma for Randomized Query Complexity

    Joshua Brody and Jae Tak Kim and Peem Lerdputtipongporn and Hariharan Srinivasulu , title =. CoRR , volume =. 2020 , url =. 2007.05580 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv 2020

  18. [18]

    Direct Sums for Parity Decision Trees , booktitle =

    Tyler Besselman and Mika G. Direct Sums for Parity Decision Trees , booktitle =. 2025 , url =. doi:10.4230/LIPICS.CCC.2025.16 , timestamp =

    work page doi:10.4230/lipics.ccc.2025.16 2025

  19. [19]

    Randomized Query Complexity of Sabotaged and Composed Functions , journal =

    Shalev Ben. Randomized Query Complexity of Sabotaged and Composed Functions , journal =. 2018 , url =. doi:10.4086/TOC.2018.V014A005 , timestamp =

    work page doi:10.4086/toc.2018.v014a005 2018

  20. [20]

    34th Computational Complexity Conference , series =

    Eric Blais and Joshua Brody , title =. 34th Computational Complexity Conference , series =. 2019 , url =. doi:10.4230/LIPICS.CCC.2019.29 , timestamp =

    work page doi:10.4230/lipics.ccc.2019.29 2019

  21. [21]

    Rahul Jain and Hartmut Klauck and Miklos Santha , title =. Inf. Process. Lett. , volume =. 2010 , url =. doi:10.1016/J.IPL.2010.07.020 , timestamp =

    work page doi:10.1016/j.ipl.2010.07.020 2010

  22. [22]

    On determinism versus unambiquous nondeterminism for decision trees , journal =

    Petr Savick. On determinism versus unambiquous nondeterminism for decision trees , journal =. 2002 , url =. TR02-009 , timestamp =

    work page 2002

  23. [23]

    Reichardt and Robert Spalek and Mario Szegedy , title =

    Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert Spalek and Mario Szegedy , title =. 2011 , url =. doi:10.1109/FOCS.2011.75 , timestamp =

    work page doi:10.1109/focs.2011.75 2011

  24. [24]

    22nd Annual

    Ben Reichardt , title =. 22nd Annual. 2011 , url =. doi:10.1137/1.9781611973082.44 , timestamp =

    work page doi:10.1137/1.9781611973082.44 2011

  25. [25]

    When Is Amplification Necessary for Composition in Randomized Query Complexity? , booktitle =

    Shalev Ben. When Is Amplification Necessary for Composition in Randomized Query Complexity? , booktitle =. 2020 , url =. doi:10.4230/LIPICS.APPROX/RANDOM.2020.28 , timestamp =

    work page doi:10.4230/lipics.approx/random.2020.28 2020

  26. [26]

    1994 , url =

    Uriel Feige and Prabhakar Raghavan and David Peleg and Eli Upfal , title =. 1994 , url =. doi:10.1137/S0097539791195877 , timestamp =

    work page doi:10.1137/s0097539791195877 1994

  27. [27]

    A Majority Lemma for Randomised Query Complexity , booktitle =

    Mika G. A Majority Lemma for Randomised Query Complexity , booktitle =. 2021 , url =. doi:10.4230/LIPICS.CCC.2021.18 , timestamp =

    work page doi:10.4230/lipics.ccc.2021.18 2021

  28. [28]

    57th Annual

    Simon Mackenzie and Abdallah Saffidine , title =. 57th Annual. 2025 , url =. doi:10.1145/3717823.3718148 , timestamp =

    work page doi:10.1145/3717823.3718148 2025

  29. [29]

    2012 , url =

    Amit Chakrabarti and Oded Regev , title =. 2012 , url =. doi:10.1137/120861072 , timestamp =

    work page doi:10.1137/120861072 2012

  30. [30]

    Sherstov , title =

    Alexander A. Sherstov , title =. Theory Comput. , volume =. 2012 , url =. doi:10.4086/TOC.2012.V008A008 , timestamp =

    work page doi:10.4086/toc.2012.v008a008 2012

  31. [31]

    Thomas Vidick , title =. Chic. J. Theor. Comput. Sci. , volume =. 2012 , url =

    work page 2012

  32. [32]

    Maximum matching in semi-streaming with few passes

    Amit Chakrabarti and Ranganath Kondapally and Zhenghui Wang , title =. Approximation, Randomization, and Combinatorial Optimization , series =. 2012 , url =. doi:10.1007/978-3-642-32512-0\_41 , timestamp =

    work page doi:10.1007/978-3-642-32512-0 2012

  33. [33]

    Indyk and D

    Piotr Indyk and David P. Woodruff , title =. 37th Annual. 2005 , url =. doi:10.1145/1060590.1060621 , timestamp =

    work page doi:10.1145/1060590.1060621 2005

  34. [34]

    11th Annual International Computing and Combinatorics Conference , series =

    Hossein Jowhari and Mohammad Ghodsi , title =. 11th Annual International Computing and Combinatorics Conference , series =. 2005 , url =. doi:10.1007/11533719\_72 , timestamp =

    work page doi:10.1007/11533719 2005

  35. [35]

    Reductions in streaming algorithms, with an application to counting triangles in graphs , booktitle =

    Ziv Bar. Reductions in streaming algorithms, with an application to counting triangles in graphs , booktitle =. 2002 , url =

    work page 2002

  36. [36]

    Buriol and Gereon Frahling and Stefano Leonardi and Alberto Marchetti

    Luciana S. Buriol and Gereon Frahling and Stefano Leonardi and Alberto Marchetti. Counting triangles in data streams , booktitle =. 2006 , url =. doi:10.1145/1142351.1142388 , timestamp =

    work page doi:10.1145/1142351.1142388 2006

  37. [37]

    40th International Colloquium on Automata, Languages, and Programming , series =

    Vladimir Braverman and Rafail Ostrovsky and Dan Vilenchik , title =. 40th International Colloquium on Automata, Languages, and Programming , series =. 2013 , url =. doi:10.1007/978-3-642-39206-1\_21 , timestamp =

    work page doi:10.1007/978-3-642-39206-1 2013

  38. [38]

    28th Annual

    John Kallaugher and Eric Price , title =. 28th Annual. 2017 , url =. doi:10.1137/1.9781611974782.116 , timestamp =

    work page doi:10.1137/1.9781611974782.116 2017

  39. [39]

    Approximation, Randomization, and Combinatorial Optimization , series =

    Rajesh Jayaram and John Kallaugher , title =. Approximation, Randomization, and Combinatorial Optimization , series =. 2021 , url =. doi:10.4230/LIPICS.APPROX/RANDOM.2021.11 , timestamp =

    work page doi:10.4230/lipics.approx/random.2021.11 2021

  40. [40]

    2014 , url =

    Andrew McGregor , title =. 2014 , url =. doi:10.1145/2627692.2627694 , timestamp =

    work page doi:10.1145/2627692.2627694 2014

  41. [41]

    T. S. Jayram and David P. Woodruff , title =. 2013 , url =. doi:10.1145/2483699.2483706 , timestamp =

    work page doi:10.1145/2483699.2483706 2013

  42. [42]

    Woodruff , title =

    David P. Woodruff , title =. 15th Annual. 2004 , url =

    work page 2004

  43. [43]

    Noga Alon and Yossi Matias and Mario Szegedy , title =. J. Comput. Syst. Sci. , volume =. 1999 , url =. doi:10.1006/JCSS.1997.1545 , timestamp =

    work page doi:10.1006/jcss.1997.1545 1999

  44. [44]

    Theory Comput

    Mark Braverman and Ankit Garg and Denis Pankratov and Omri Weinstein , title =. Theory Comput. Syst. , volume =. 2016 , url =. doi:10.1007/S00224-015-9655-Z , timestamp =

    work page doi:10.1007/s00224-015-9655-z 2016

  45. [45]

    Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications , journal =

    Iordanis Kerenidis and Sophie Laplante and Virginie Lerays and J. Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications , journal =. 2015 , url =. doi:10.1137/130928273 , timestamp =

    work page doi:10.1137/130928273 2015

  46. [46]

    Communication Complexity: and Applications , publisher=

    Rao, Anup and Yehudayoff, Amir , year=. Communication Complexity: and Applications , publisher=

    work page

  47. [47]

    Woodruff and Qin Zhang , title =

    Alexandr Andoni and Jiecao Chen and Robert Krauthgamer and Bo Qin and David P. Woodruff and Qin Zhang , title =. Innovations in Theoretical Computer Science , pages =. 2016 , url =. doi:10.1145/2840728.2840753 , timestamp =

    work page doi:10.1145/2840728.2840753 2016

  48. [48]

    Razborov

    Alexander A. Razborov , title =. Theor. Comput. Sci. , volume =. 1992 , url =. doi:10.1016/0304-3975(92)90260-M , timestamp =

    work page doi:10.1016/0304-3975(92)90260-m 1992

  49. [49]

    1992 , url =

    Bala Kalyanasundaram and Georg Schnitger , title =. 1992 , url =. doi:10.1137/0405044 , timestamp =

    work page doi:10.1137/0405044 1992

  50. [50]

    PyMatting: A Python Library for Alpha Matting

    Piotr Indyk and David P. Woodruff , title =. 44th Symposium on Foundations of Computer Science , pages =. 2003 , url =. doi:10.1109/SFCS.2003.1238202 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/sfcs.2003.1238202 2003

  51. [51]

    Eric Blais and Joshua Brody and Kevin Matulef , title =. Comput. Complex. , volume =. 2012 , url =. doi:10.1007/S00037-012-0040-X , timestamp =

    work page doi:10.1007/s00037-012-0040-x 2012

  52. [52]

    Testing Probability Distributions using Conditional Samples , journal =

    Cl. Testing Probability Distributions using Conditional Samples , journal =. 2015 , url =. doi:10.1137/130945508 , timestamp =

    work page doi:10.1137/130945508 2015

  53. [53]

    Amortized Communication Complexity , journal =

    Tom. Amortized Communication Complexity , journal =. 1995 , url =. doi:10.1137/S0097539792235864 , timestamp =

    work page doi:10.1137/s0097539792235864 1995

  54. [54]

    Anurag Anshu and Dmitry Gavinsky and Rahul Jain and Srijita Kundu and Troy Lee and Priyanka Mukhopadhyay and Miklos Santha and Swagato Sanyal , title =. 37th. 2017 , url =. doi:10.4230/LIPICS.FSTTCS.2017.10 , timestamp =

    work page doi:10.4230/lipics.fsttcs.2017.10 2017

  55. [55]

    Innovations in Theoretical Computer Science , pages =

    Avishay Tal , title =. Innovations in Theoretical Computer Science , pages =. 2013 , url =. doi:10.1145/2422436.2422485 , timestamp =

    work page doi:10.1145/2422436.2422485 2013

  56. [56]

    Ashley Montanaro , title =. Chic. J. Theor. Comput. Sci. , volume =. 2014 , url =

    work page 2014

  57. [57]

    Agarwala and I

    Shalev Ben. Direct Product Theorems for Randomized Query Complexity , booktitle =. 2025 , url =. doi:10.1109/FOCS63196.2025.00038 , timestamp =

    work page doi:10.1109/focs63196.2025.00038 2025

This paper was first reviewed by glm-5.2 on July 9, 2026.