Pith. sign in

REVIEW 2 major objections 4 minor 3 references

Strong XOR Lemma for Information Complexity

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read A strong XOR lemma for information complexity: computing f⊕n with constant error costs Ω(n) times the information needed to compute f with error n^{-1}, up to vanishing additive terms.

desk verdict The main theorem is false for balanced functions such as XOR: the proof's Claim 52 confuses the protocol's success probability with the bias of the function value, and the n-fold XOR of XOR is computable with 1 bit of information. read the letter →

arxiv 2411.13015 v2 pith:GJOAVL4F submitted 2024-11-20 cs.CC cs.ITmath.IT

Pachara Sawettamalya , Huacheng Yu This is my paper · ORCID
classification cs.CCcs.ITmath.IT MSC 68Q1794A17
keywords strongXORlemmainformationcomplexitycommunicationrandomizedprotocolsdirectsumdistributionalcostprotocoldecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

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 tries to prove a strong XOR lemma for information complexity in two-player randomized communication: for any boolean function f, computing the n-fold XOR f⊕n with constant error forces the players to reveal Ω(n) times as much information as computing f with error O(1/n), up to vanishing additive terms. If true, the simple 'compute each copy separately, then XOR the answers' protocol is asymptotically optimal in information, and the error trade-off between 1/n for f and constant for f⊕n is tight. The proof introduces a conditional binary protocol decomposition that recursively splits a protocol for n copies into two protocols for n/2 copies while preserving a multiplicative decomposition of advantage and an additive decomposition of information cost. A reader should care because information complexity is a proxy for how much private input must be exposed, and this gives a rare parameter regime where naive parallelism is provably optimal.

What carries the argument

The main object is the conditional binary protocol decomposition. Given a protocol π for f⊕n over μ^n whose pointwise advantage Z = adv(f⊕n | X0,Y1,M) is at least a constant α on an event W, the authors condition on W, split coordinates in half, and obtain two generalized protocols π0 and π1 for f⊕(n/2); the rectangle property of communication protocols makes the advantages multiply (Z = A0A1) and the information costs add (I0+I1 ≈ I). Recursing to leaves yields n protocols for f; a distribution D with weight proportional to the probability of all conditioning events is used to average, and standardization converts the chosen generalized leaf protocol into a standard one at a cost controlled by its θ-cost, the KL-divergence from its standardization.

What would settle it

Compute both sides of the Claim 63 inequality for a small explicit protocol (e.g., n=2, f the AND or equality function) over all transcripts; if the right-hand side is ever smaller than the left-hand side, the lemma fails. A coarser falsifier is to find f with IC(f,$n^{{-1}}$) = log|X||Y| + Ω(1) yet IC(f⊕n,1/10) ≤ c n log|X||Y| with c < c1, which would contradict Theorem 2 before the additive terms dominate.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2: there are universal constants λ∈(0,1) and c1>0 such that IC(f⊕n,1/10) ≥ c1 n (IC(f,$n^{{-1}}$) − log(|X||Y|)/n^λ − 1). The paper simultaneously proves the matching upper bound IC(f⊕n,1/10) ≤ c2 n IC(f,$n^{{-1}}$) (Theorem 3), so the two-sided result pins the information cost of XOR to within a vanishing additive term. The engine is a distributional version (Theorem 4) stating IC_{μ^n}(f⊕n,1/10) ≥ c3 n (IC_μ(f,$n^{{-λ}}$) − log(|X||Y|)/n^λ − 1) for every input distribution μ. The error parameter $n^{{-1}}$ in the single-copy task is essential: the usual embedding argument only preserves constant error, and this paper pushes it down to polynomial error.

Load-bearing premise

Everything collapses if the sketched inequality in Claim 63—bounding the θ-cost of the conditioned, decomposed protocol by (1/p_S)(Θ_S + H(p_S))—turns out false, because the leaf protocol's closeness to a standard protocol is exactly what the standardization step needs.

Editorial extensions

If this is right

  • The naive protocol—evaluate each f(Xi,Yi) independently with error 1/n and XOR the answers—is within a constant factor and a vanishing additive loss of optimal in information, not just in communication length.
  • The error trade-off (1/n for f, constant for f⊕n) is asymptotically tight: no constant-error protocol for f⊕n can be cheaper than Ω(n) times the information needed to solve f at polynomial error.
  • The distributional version holds for every input distribution μ, so the lower bound is robust to worst-case inputs.
  • The boosting lemma used in the proof transfers the result from error n^{-λ} to n^{-1} in the information-complexity statement.

Reading between the lines

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

  • Inference: the same conditional-decomposition machinery plausibly yields strong direct product theorems for information complexity, since the leaf protocols already have product-form error and additive cost.
  • Inference: the exponentially-small-advantage regime is genuinely blocked by the paper's own counterexample in Section 1.2, so any extension there would need a different resource measure than plain internal information.
  • Inference: a testable refinement is to reduce or remove the additive log(|X||Y|)/n^λ loss, which would make the bound tight up to o(1) for all domain sizes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper claims a strong XOR lemma for information complexity in the two-player randomized communication model: for every f and n, IC(f^⊕n, 1/10) ≥ c1 n (IC(f, n^{-1}) - log(|X||Y|)/n^λ - 1). The proof proceeds via a distributional version (Theorem 4) and a main decomposition lemma (Lemma 8) that, given a protocol for f^⊕n with error 1/10 and information cost I, constructs a protocol for f with error n^{-λ} and cost O(I/n + log(|X||Y|)/n^λ + 1). The decomposition is a recursive 'conditional binary decomposition' of the protocol tree, with potential arguments over quantities ε_S, p_S, χ_S, information cost, and θ-cost, followed by standardization (Lemma 65). The paper also proves a matching upper bound (Theorem 3) and observes that an XOR lemma for exponentially small advantage is false.

Significance. If correct, the result would be a substantial and tight strengthening of the folklore embedding bound of BBCR10: it would show that computing n independent XOR copies needs Ω(n) times the information needed to compute f at polynomially small error, up to vanishing additive losses. The paper's framework—conditional protocol decomposition, θ/γ-cost, standardization via correlated sampling—is a coherent toolkit, and the upper bound Theorem 3 is a clean independent argument. However, the central lower-bound proof contains a false inequality (Claim 52) that invalidates the recursion; the main theorems are therefore not established by the manuscript.

major comments (2)
  1. [Section 7, Claim 52] Claim 52 is false, and its proof conflates two different notions of advantage. The quantity ε_S is defined (Table 1) as the protocol's disadvantage 1 - adv_{π_S}(f^⊕(X_S,Y_S)), which for an error-1/10 protocol is 4/5 on the output bit. The random variable Z_S = adv_{π_S}(f^⊕(X_S,Y_S) | X_{S0},Y_{S1},M_S) is the conditional advantage of the function value, not of the protocol's output. The step E(Z_S) ≥ 1 - ε_S would require that the expected conditional advantage of the function value dominate the output advantage, which is false. Concretely, take μ uniform on {0,1}^2, f(x,y)=x⊕y, n=2, and let π be: Alice sends a=x_1⊕x_2 with probability 0.8 and a null symbol with probability 0.2; if a is sent Bob outputs a⊕y_1⊕y_2, otherwise he outputs a uniform bit. This protocol errs with probability exactly 1/10, has information cost 0.8, and has the rectangle property. For S=∅, conditioning on (X_0,Y_1,M) leaves at least one of X_1 or Y_0 uniform and independent of the transcript, so f^⊕2 is uniform given (X_0,Y_1,M); hence Z=0 pointwise and E(Z)=0, while ε=1/5. Thus the claimed inequality fails, the event W={Z≥α} has probability 0, and the quantities p_S, χ_S used in Claims 55, 59, 60, 63 and Lemmas 56-57 are undefined or zero. Since Lemma 8, Theorem 4, and Theorem 2 all rest on this decomposition, the main lower-bound proof is invalid. This example does not disprove the theorem statement, but it shows that Lemma 8's proof does not apply even to the simplest nontrivial function.
  2. [Section 7, Lemma 51 and Claim 63] Even setting aside Claim 52, the manuscript leaves load-bearing inequalities in the recursive step unproved. Lemma 51(iv) and (v) are asserted with a reference that they 'closely follow' Claims 48 and 49, but their quantitative forms (ε_S0+ε_S1 ≤ (2/(1+√α))(1-E(Z_S|W_S)) and p_S ≥ (1-ε_S-α)/(E(Z_S|W_S)-α)) are exactly what is used in the potential argument of Claim 55 and in Lemmas 56 and 57. Similarly, the 'patching' step in the proof of Claim 63, which replaces each conditioned message denominator π(M_i | X M_{<i} W_S) by π(M_i | X M_{<i}), is only one sentence; the θ-cost bound is then used in Lemma 64 and in Lemma 8's error bound. These are not routine typos: they are substantial missing arguments in the main technical chain, and a revision would need complete proofs of these inequalities.
minor comments (4)
  1. [Section 7.3, Claim 52] In the displayed proof of Claim 52, the inequality contains Pr(W_S) · E(Z_S | W_S) + Pr(W_S) · E(Z_S | W_S); the second term should condition on the complement of W_S. Correcting this typo does not fix the substantive error described in Major Comment 1.
  2. [Section 7.1, Claim 49] The sentence 'By definition, W implies Z ≤ α' has the implication backwards; it is the complement of W that implies Z ≤ α (or Z < α).
  3. [Section 7 and Lemma 8] Lemma 8 and the main theorems are stated for arbitrary positive integers n, while the recursive procedure in Section 7 assumes n = 2^m. The paper does not spell out how general n is reduced to this case, for example by padding coordinates, and how the additive error terms are affected.
  4. [Section 3.1] The text states that 'the advantage of π is at most E(Z)' immediately after defining A0, A1, and Z. This is the first appearance of the conflation between the protocol output advantage and the conditional advantage of the function value; the statement should be corrected or removed.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the XOR-lemma lower bound follows from a self-contained protocol-conversion lemma, and self-citations to [Yu22] are used as tools, not as the theorem being proved.

full rationale

The paper's central derivation is a reduction: Lemma 8 assumes a protocol π for f^⊕n with error 1/10 and information cost I, and constructs a standard protocol η for f with error n^{-λ} and information cost C(I/n + log(|X||Y|)/n^λ + 1). The construction is carried out in Sections 7-8: a recursive conditional decomposition defines protocols πS, and a standardization argument (Lemmas 62, 64, 65) converts the selected generalized protocol into a standard one. Every bound used in this chain is either proved in the paper (Claims 46-49, 52-63, Lemmas 56, 57, 64, 65) or is an external standard tool (Pinsker, correlated sampling, Braverman's minimax theorem). Theorem 4 follows by instantiating Lemma 8 with I = IC_{μ^n}(f^{⊕n},1/10) and rearranging; no fitted parameter is later renamed as a prediction. Theorem 2 follows from Theorem 4 plus the minimax theorem and Lemma 66, and Theorem 3 is an independent direct upper bound by running n copies of the optimal protocol for f. The citations to [Yu22] identify the decomposition idea and the rectangle-property definitions, but the partial rectangle property, its preservation under decomposition, and the θ/γ-cost linearity are defined and proved in this paper; no 'uniqueness theorem' or unproved self-citation is invoked to force the choice of conditional decomposition. The skeptical concern about Claim 52 is a potential correctness gap in a technical lemma, not a circularity: even if the proof of E(Z_S|W_S) ≥ 1−ε_S were flawed, that would invalidate Lemma 8 rather than make it equivalent to its input. Similarly, the sketch-level 'patching' step in Lemma 62 is a completeness issue, not a case of the conclusion being assumed as an input. The paper is self-contained against external benchmarks except for standard prior results, and the claimed lower bound does not reduce by construction to IC(f,n^{-1}) or to [Yu22].

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The proof uses standard information-theoretic tools and communication complexity definitions. No empirical fits or invented entities. The constants alpha, tau, lambda are universal constants chosen for the argument, not fitted to data.

free parameters (3)
  • alpha = 3/5
    Chosen as 1 - 2ε where ε = 1/5 is the disadvantage of the initial protocol; a universal constant, not fitted to data.
  • tau = approximately 0.172
    Defined by (1+sqrt(alpha))/2 = 2^{-tau}; derived from alpha, used in the potential argument.
  • lambda = small universal constant in (0,1)
    Appears in the standardization bound (Lemma 65) to absorb the n^{-(1-tau)} terms; chosen for the proof, not fitted to data.
assumptions (4)
  • standard math Standard information theory: chain rule, subadditivity, Pinsker's inequality.
    Used throughout, e.g., Fact 10, Lemma 17, Definition 13.
  • standard math Rectangle property of standard communication protocols.
    Fact 29, foundational to the decomposition lemmas.
  • domain assumption Braverman's minimax theorem relating IC and ICD (Theorem 24).
    Used in the proof of Theorem 2 to pass from distributional to worst-case information complexity.
  • ad hoc to paper Infima in the definitions of IC and IC_mu are attained.
    Explicitly assumed for convenience in Section 9; the authors note it can be relaxed by considering convergent sequences of protocols.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strong XOR Lemma for Information Complexity." pith.science (2026). https://pith.science/paper/GJOAVL4F

@misc{pith2026241113015,
  author       = {Pith},
  title        = {Pith review of: Strong XOR Lemma for Information Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GJOAVL4F}},
  note         = {Machine review of arXiv:2411.13015}
}
abstract

For any $\{0,1\}$-valued function $f$, its \emph{$n$-folded XOR} is the function $f^{\oplus n}$ where $f^{\oplus n}(X_1, \ldots, X_n) = f(X_1) \oplus \cdots \oplus f(X_n)$. Given a procedure for computing the function $f$, one can apply a ``naive" approach to compute $f^{\oplus n}$ by computing each $f(X_i)$ independently, followed by XORing the outputs. This approach uses $n$ times the resources required for computing $f$. In this paper, we prove a strong XOR lemma for \emph{information complexity} in the two-player randomized communication model: if computing $f$ with an error probability of $O(n^{-1})$ requires revealing $I$ bits of information about the players' inputs, then computing $f^{\oplus n}$ with a constant error requires revealing $\Omega(n) \cdot (I - 1 - o_n(1))$ bits of information about the players' inputs. Our result demonstrates that the naive protocol for computing $f^{\oplus n}$ is both information-theoretically optimal and asymptotically tight in error trade-offs.

Figures

Figures reproduced from arXiv: 2411.13015 by the authors.

Figure 1
Figure 1. A protocol η for computing f on inputs (x, y) ∼ µ via the embedding method. The protocol η can also be interpreted as follows: we list n protocols (π1, . . . , πn) for which πj corresponds to η | J = j, and execute a πj for a random j ∈ [n]. It can be shown by calculation that the information costs of these n protocols sum up to at most I + O(n). Since η picks a uniform random coordinate j and runs πj , its informat… view at source ↗
Figure 2
Figure 2. A single-level “conditional” decomposition of a protocol [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. The “conditional” decomposition of π into π0 and π1. 21 [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: The conditional decomposition procedure of [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]
Figure 5
Figure 5. Figure 5: A recursive procedure begins with a standard protocol [PITH_FULL_IMAGE:figures/full_fig_p024_5.png]
Figure 6
Figure 6. Figure 6: The “proportional” distribution D for sampling an index S ∈ {0, 1} m. We wish for these properties for the protocol πS. Lemma 58 (Decomposition Lemma; informal). Over the distribution S ∼ D, the generalized protocol πS has the following properties in expectation. (1) π…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 2 canonical work pages

  1. [2]

    Summing this over 0 ≤ k ≤ m − 1 = log2 n − 1 yields: m−1X k=0 X |S|=k H(pS) = O(nτ log n) as wished

    Furthermore, we can derive: X |S|=k H(pS) = X |S|=k H(1 − pS) ≤ 2k · H  2−k · X |S|=k (1 − pS)   (H is concave) ≤ 2k · H 2−(1−τ )k−1 (H is increasing in (0, 1/2]) ≤ 2k · 2 · H 2−(1−τ )k−1 (H(x) ≤ 2 · p log 1 p for p ∈ (0, 1/2]) = 2τ k· ((1 − τ )k + 1)) ≤ 2τ k· (k + 1). Summing this over 0 ≤ k ≤ m − 1 = log2 n − 1 yields: m−1X k=0 X |S|=k H(pS) = O(nτ ...

    work page

  2. [1982]

    Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract)

    IEEE Computer Society, 1982, pp. 80–91. 38 [Yu22] Huacheng Yu. “Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract)”. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022. IEEE, 2022, pp. 1186–1192. A Missing Proofs We will restate and provide the missing proo...

    work page 1982

  3. [2007]

    A Technique for Hardness Amplification Against AC0

    Ed. by David S. Johnson and Uriel Feige. ACM, 2007, pp. 411–419. 37 [Hoz24] William M. Hoza. “A Technique for Hardness Amplification Against AC0”. In: 39th Computational Complexity Conference (CCC 2024) . Ed. by Rahul Santhanam. V ol. 300. Leibniz International Pro- ceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f ...

    arXiv 2024

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.