{"id":"64eeb8b9-6e3f-4400-9d1c-1a42f08f5174","arxiv_id":"2411.13015","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A strong XOR lemma for information complexity: computing f^{⊕n} with constant error costs Ω(n) times the information needed to compute f with error 1/n, up to vanishing additive terms.","lead":"Computing the XOR of n copies of a function provably costs about n times as much information as computing the function once, even when the single-copy error is as large as 1/n. This confirms that the obvious 'solve each copy and XOR' protocol is information-theoretically optimal.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 8's recursive decomposition assumes the base function value f^{⊕n} has constant advantage over µn (Section 7 sets ε = 1/5, α = 1−2ε), but this is false for balanced f such as f(x,y)=x⊕y, so Claim 52 and the whole conditioning argument are not justified.","rationale":"The reader's conditional verdict focused on Claim 63's 'patching' argument, which is a technical step that appears repairable. The more load-bearing concern is upstream: the recursive decomposition requires the base function value f^{⊕n} to have constant advantage over the input distribution µn, but for any balanced function f (e.g., XOR) and product distribution µn, adv_{µn}(f^{⊕n}) = 0, so ε = 1, α = 1−2ε = −1, and the entire conditioning framework breaks. The proof incorrectly equates the protocol's error probability (1/10 ⇒ ε = 1/5) with the bias of the function value, which can be zero even when the protocol succeeds with high probability. A concrete protocol for f=x⊕y, n=2, with error 0.1 and information cost 0.8 yields E[Z] = 0, directly contradicting Claim 52's E[Z] ≥ 4/5. This means Lemma 8, as stated and proved, does not cover a large class of functions and distributions. While the final theorem's statement may still be true (for this example the additive −1 makes the bound vacuous), the proof of the central technical lemma is invalid as written, so the paper's main claims are not established by the present argument. The concern is not about disagreement with consensus or about style; it is an internal inconsistency in the proof's setup.","tokens_in":39039,"tokens_out":39485,"duration_ms":346931,"concrete_test":"Implement the counterexample: f(x,y)=x⊕y, µ uniform over {0,1}², n=2, and the protocol π that with probability 0.8 Alice sends a = x1⊕x2 (Bob outputs a⊕y1⊕y2) and with probability 0.2 Alice sends nothing (Bob outputs a uniform random bit). Verify that π errs with probability 0.1 and has information cost 0.8. Then compute the quantity Z = adv(f^{⊕2}(X1,X2,Y1,Y2) | X1, Y2, M) used in Section 7.1. For every value of (X1,Y2,M), the function value is a uniform bit independent of the conditioning (since Y1 or X2 remains uniform), so Z = 0 and E[Z] = 0, contradicting the proof's requirement E[Z] ≥ 1−ε = 4/5. This shows the base case of Claim 52 and the subsequent decomposition argument fail for a valid instance of Lemma 8.","verdict_should_be":"REJECT","load_bearing_attack":"The proof of Lemma 8 (Section 7) sets ε = 1/5 and α = 1−2ε, treating ε as the 'disadvantage' of the protocol. The protocol's error 1/10 only implies that the prediction advantage of f^{⊕n} given the full transcript and full inputs (X,Y,M) is at least 4/5; it does not imply that the bias advantage adv(f^{⊕n} | X0,Y1,M) has expectation at least 4/5. Claim 52 asserts E[Z_S] ≥ 1−ε_S, and for the base case S=∅ this would require E[adv(f^{⊕n} | X0,Y1,M)] ≥ 4/5. However, conditioning on fewer variables can dramatically reduce the advantage. Concretely, let f(x,y)=x⊕y over uniform µ, n=2, and use the protocol where Alice sends x1⊕x2 with probability 0.8 and nothing with probability 0.2, while Bob outputs the parity of his bits with Alice's bit, or a uniform random bit when Alice sends nothing. This protocol errs with probability exactly 0.1 and has information cost 0.8. For this protocol, conditioned on (X0=x1, Y1=y2, M), the remaining unknown Y1 (or X2) makes f^{⊕2} uniform, so Z = 0 pointwise and E[Z] = 0. Thus Claim 52's inequality E[Z] ≥ 4/5 fails, α = 3/5 is not a valid threshold, and Claims 48, 49, the potential argument in Claim 55, and hence the existence of a good leaf protocol all collapse. This is a fundamental gap in the main technical lemma, not a minor missing detail.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39440,"tokens_out":14275,"duration_ms":139045,"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":[{"comment":"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.","section":"Section 7, Claim 52"},{"comment":"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.","section":"Section 7, Lemma 51 and Claim 63"}],"minor_comments":[{"comment":"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.","section":"Section 7.3, Claim 52"},{"comment":"The sentence 'By definition, W implies Z ≤ α' has the implication backwards; it is the complement of W that implies Z ≤ α (or Z < α).","section":"Section 7.1, Claim 49"},{"comment":"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.","section":"Section 7 and Lemma 8"},{"comment":"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.","section":"Section 3.1"}],"recommendation":"reject","confidential_remarks":"The counterexample in Major Comment 1 is not a pathological corner case: f(x,y)=x⊕y over the uniform distribution satisfies every hypothesis of Lemma 8 for n=2, and the protocol described has the rectangle property, exactly the structure used throughout the proof. The failure of Claim 52 is therefore internal to the paper's decomposition methodology, not a missing edge case in a statement. In my judgment this cannot be repaired by local edits; the conditioning decomposition would need to be redesigned, for instance by conditioning on a player's full view rather than on a mixed partial transcript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is not correct as written, and the problem is not a missing detail. For f(x,y)=x⊕y, the n-fold XOR is just the parity of 2n bits. Alice sends the parity of her n bits; Bob XORs with the parity of his. That's one bit of communication, zero error, information cost 1. So IC(XOR^{⊕n},1/10) ≤ 1. Meanwhile IC(XOR,n^{-1}) is 1 - o(1), because any protocol with error 1/n must transmit roughly one bit (the binary symmetric channel capacity is 1 - H(1/n)). Theorem 2 would then force IC(XOR^{⊕n},1/10) ≥ c1·n·(1 - o(1)), which is false. This is not a subtle counterexample; it kills the stated result.\n\nThe source of the error is exactly what your stress-test flags. Claim 52 proves E(Z_S) ≥ adv_{π_S}(f) and then writes adv_{π_S}(f) = 1 - ε_S. But adv_{π_S}(f) is the advantage of the function value under the input distribution, not the advantage of the protocol's output. For balanced f, adv(f)=0 even when the protocol is correct with probability 9/10. Your example protocol (Alice sends x1⊕x2 with probability 4/5) realizes error 0.1, and conditioned on (X0,Y1,M) the remaining coordinates make f uniform, so Z=0 pointwise and the event W is empty. Claim 52's E[Z|W] ≥ 4/5 cannot hold because W has probability zero. The conditional decomposition therefore has nothing to condition on, and the whole potential argument in Claim 55 collapses.\n\nI want to give credit where it is earned. Theorem 3 (the upper bound) is standard and correct, and the exposition is clear: the paper explains the relationship to Yu22 honestly, and the self-citation is appropriate. The conditional-decomposition idea is creative, and the algebraic machinery in Sections 7-8 might be repairable if the statement were restricted to functions with non-negligible bias. But as stated, the main theorem has a straightforward counterexample, and the proof's central inequality is false for balanced functions.\n\nThis is not a paper to send to a serious referee in its current form. It needs either a fundamental reformulation (excluding functions like XOR, or replacing the information-complexity measure with something that avoids the parity collapse) or a genuinely different proof. I would not cite it, and I would not put it in the reading group except as a warning about how error probability and function bias get conflated in decomposition arguments.","headline":"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.","tokens_in":39953,"tokens_out":13309,"would_cite":false,"duration_ms":139315,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["strong XOR lemma","information complexity","communication complexity","randomized protocols","direct sum","distributional information cost","protocol decomposition"],"falsifier":"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.","tokens_in":38827,"feed_emoji":"🧮","tokens_out":4967,"duration_ms":49117,"temperature":0.7,"pith_summary":"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.","feed_headline":"XOR of n copies needs n times the information","feed_subtitle":"A new proof shows the naive evaluate-each-copy-then-XOR protocol is optimal in information up to vanishing losses.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the binary protocol decomposition and the view that information and advantage decompose under coordinate splitting, which the conditional decomposition modifies.","marker":"[Yu22]"},{"why":"Provides the embedding protocol (Theorem 6) that yields the constant-error XOR lemma, the baseline whose error regime this paper improves.","marker":"[BBCR10]"},{"why":"Supplies the definitions of distributional and max-distributional information complexity plus the minimax theorem (Theorem 24) used to pass to worst-case information complexity.","marker":"[Bra15]"},{"why":"Provides the correlated-sampling lemma (Lemma 45) that converts statistical closeness into a coupling, used in the standardization step.","marker":"[RY20]"},{"why":"Origin of the embedding/information-statistics approach that [BBCR10] makes explicit; the additive-error baseline is inherited from this line.","marker":"[BJKS04]"}],"fun_headline_variants":["Strong XOR lemma: n copies cost n× info","XOR blowup: information cost scales linearly","Tight XOR lemma: n× the information for n copies","Proving XOR needs n times the information","Information complexity: XOR multiplies cost by n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Strong XOR lemma: n copies cost n× info","XOR blowup: information cost scales linearly","Tight XOR lemma: n× the information for n copies","Proving XOR needs n times the information","Information complexity: XOR multiplies cost by n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000187,"raw_usage":{"total_tokens":1340,"prompt_tokens":968,"completion_tokens":372,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":584,"completion_tokens_details":{"reasoning_tokens":308}},"tokens_in":584,"tokens_out":372,"duration_ms":4245,"temperature":1.0,"reasoning_tokens":308,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:56:06.556340+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}