{"id":"c717bbbe-698e-4c8d-9a39-e5e27805310c","arxiv_id":"2412.06552","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Randomized parity decision trees satisfy direct sum theorems for lower bounds from discrepancy or product distributions, via a new skew complexity measure with perfect direct sum.","lead":"This paper proves the first direct sum theorems for randomized parity decision trees, showing that solving k independent copies costs at least roughly k times the single-copy cost when the lower bound comes from the discrepancy method or from a product distribution. It introduces a skew complexity measure that satisfies a perfect direct sum and may be useful beyond this model.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 23's third equality is not merely unproved: as an identity of randomized trees it is false, so the perfect direct sum for the skew measure currently lacks a valid proof of the cost step.","rationale":"After reading the full manuscript, the main results are otherwise well supported. Theorem 1's discrepancy direct sum is a clean Fourier argument (Lemma 8, Claim 9, Lemma 7). The extraction lemma (Claim 21) is proved carefully, and Lemma 22's error analysis is sound. The conversion theorems (Theorems 18 and 19) have detailed proofs modulo standard folklore used for FFO. The only serious spot is Lemma 23. The equality of processes claimed there is not a restatement of a standard property; it is the key to the perfect direct sum for the skew measure. In fact a simple example shows the commutation is false as an identity of randomized trees, so the proof as written has a real hole. Since the cost inequality itself seems plausible and may be provable directly, we do not recommend rejection; but the manuscript should either replace the unjustified equality with a proof of the cost identity or weaken Theorem 17 until such a proof is supplied. This matches the reader's CONDITIONAL verdict, with the concern sharpened from 'unproved but plausible' to 'false as stated and requiring a different proof.'","tokens_in":35989,"tokens_out":31088,"duration_ms":330607,"concrete_test":"Independently re-derive Lemma 23 without invoking the commutation equality: prove directly that for every deterministic tree T and every partial fixing ρ, ∑_i q(Ext_i(T_ρ), U_{ρ_i}) ≤ q(T_ρ, U_ρ), and then justify the reordering of expectation over ρ_i and ρ_{−i} by a bijection between remaining critical pure queries and queries surviving in T_ρ. As a computational check, enumerate all deterministic parity trees of depth ≤4 on k=2, n=2 and all partial fixings ρ, and compare the two sides of the third equality in Lemma 23; any mismatch in expected query cost would falsify Theorem 17, whereas the existence of a direct proof would resolve the gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.2, Lemma 23: the third equality in the proof asserts that applying Ext and fixing variables commute: (Ext_i(T_{eρ}))_{ρ_i} = Ext_i(T_ρ), with eρ obtained from ρ by setting ρ_i = ⋆^n. This equality is load-bearing: it is the only step that yields the per-copy cost bound ∑_i sq(T_i, µ) ≤ sq(T, µ^k), hence Theorem 17, on which Theorem 2 rests. The paper gives no proof, and the assertion is actually false as an equality of randomized trees. Counterexample: k=2, n=1; take a deterministic T that queries x_1, then x_2, and in the x_1=0 branch labels the x_2=0 leaf (0,0) and the x_2=1 leaf (1,1) (such an incorrect tree is allowed in Lemma 23, which applies to arbitrary deterministic T). For ρ=(0,0), T_ρ is the single leaf (0,0), so Ext_1(T_ρ) deterministically outputs 0. For eρ=(0,⋆), T_{eρ} queries only x_2; Ext_1(T_{eρ}) has no critical copy-1 query and therefore outputs 0 or 1 each with probability 1/2; pruning by ρ_1=0 does not change this distribution. Thus the two processes differ. What is needed is a direct proof of the cost identity that the proof actually uses: E_{ρ∼R^k} q(Ext_i(T_ρ), U_{ρ_i}) = E_{ρ_i, eρ} q((Ext_i(T_{eρ}))_{ρ_i}, U_{ρ_i}), which is plausible and likely true because pruning deletes exactly the pure copy-i queries whose coordinates are fixed by ρ_i. As written, however, Lemma 23 is not proved, and Theorem 17—the central engine of the paper—is contingent on a repair.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies direct sum theorems for randomized parity decision trees, asking whether R(f^k) ≥ Ω(k)·R(f) holds in the R^pt model. It proves two incomparable results. Theorem 1 gives R(f^k) ≥ Ω(k)·disc(f) for every f, via a Fourier-analytic characterization of parity discrepancy and an XOR lemma for disc. Theorem 2 gives R(f^k) ≥ Ω(k/log n)·D^×(f), where D^×(f) is the best distributional lower bound achievable with a product distribution; the proof introduces a new measure S_ε(f, μ) called skew complexity, claims a perfect direct sum for S, and relates S to D^× up to O(log n) factors. The paper also proves separations showing that disc and D^× are incomparable, and that the log-factor loss in the S-to-D^× conversion is necessary for the approach.","tokens_in":36383,"tokens_out":9715,"duration_ms":100779,"significance":"If the central technical claim is repaired, this is a substantial contribution. The discrepancy part is self-contained and elegant: Lemma 8 and Claim 9 give a clean Fourier proof of Lemma 7, and Theorem 1 follows. The skew measure S_ε is a novel and potentially reusable tool for product-distribution lower bounds in parity decision trees, and the two-way inequalities with D^× are nontrivial. The paper is also candid about the logarithmic losses and about the main open question. The main concern is that the perfect direct sum for S, which is the engine behind Theorem 2, rests on an unproved and in general false commutation assertion in Lemma 23; this needs to be fixed before the main claims can be accepted.","major_comments":[{"comment":"The third equality in the chain proving ∑_i sq(T_i, μ) ≤ sq(T, μ^k) is asserted with the explanation that applying Ext and fixing variables commute, but this commutativity is not proved and, as an equality of randomized trees, it is false. For k=2, n=1, take a deterministic tree T that queries x1, then x2, and in the x1=0 branch labels the x2=0 leaf (0,0) and the x2=1 leaf (1,1); the other branch can be completed arbitrarily. For ρ=(0,0), T_ρ is the single leaf (0,0), so Ext_1(T_ρ) outputs 0. For eρ=(0,⋆), T_{eρ} queries only x2; Ext_1(T_{eρ}) has no critical copy-1 query and therefore outputs 0 or 1 with probability 1/2 each, and pruning by ρ1=0 does not change that distribution. The counterexample tree is not a correct computation of f^k, but the proof of Lemma 23 is stated for arbitrary deterministic trees and uses no correctness property, so the commutation claim fails in the generality needed. What is actually needed is a direct proof of the cost expectation identity E_{ρ_i,eρ} q((Ext_i(T_{eρ}))_{ρ_i}, U_{ρ_i}) = E_ρ q(Ext_i(T_ρ), U_{ρ_i}); this is plausible but is not supplied. Since this cost inequality is the only step leading to Theorem 17, and Theorem 17 underlies Theorems 11, 13, and ultimately Theorem 2, the main technical claim is not established as written. I regard this as repairable rather than fatal, but the repair must appear in the manuscript.","section":"§5.2, Lemma 23"}],"minor_comments":[{"comment":"The statement and proof use inconsistent parameters: the statement says D_{ε+δ}(f, μ) ≤ D_ε(f, μ)/δ, but the proof bounds the depth by d/γ and the error by ε+γ. Please make the parameters consistent.","section":"§A.4, Claim 10"},{"comment":"The final equality writes rank(Q^{⪯v}_{S(p′,⋆)}) = |S(p,⋆)|; the right-hand side should be |S(p′,⋆)|, since S(p′,⋆) = S(p,⋆) ∪ {j}.","section":"§6, Lemma 25, last case"},{"comment":"The sentence 'Since all those calls are completed successfully with probability ≥ γ' should read 'with probability ≥ 1−γ' (or use equivalent union-bound language), and the proof of Theorem 18 writes O(log(n)/γ) where the statement calls for O(log(n/γ)).","section":"§6.2, Lemma 31 and Theorem 18"},{"comment":"The final reduction R(f,ε) ≤ O(D_NOR(f)+log(1/ε)) is invoked as a re-interpretation of [HR24] without a proof or a precise statement; since Lemma 29 is used at line 4 of Algorithm 5, a full derivation or exact citation would strengthen the paper.","section":"Appendix A.4, Lemma 29"}],"recommendation":"major_revision","confidential_remarks":"I agree with the stress-test concern: the third equality in Lemma 23 is false as an identity of randomized trees, and the proof of the cost bound needs repair. I do not see evidence that the final cost inequality is false; the natural repair via a direct expectation identity is likely within scope. The authors should be asked to supply that proof, together with the small parameter fixes listed in the minor comments, before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper gives the first direct sum theorems for randomised parity decision trees. The discrepancy result (Theorem 1) is clean: discrepancy for this model has a Fourier characterisation, and the XOR lemma for discrepancy falls out of the tensor product of Fourier coefficients. That part is solid and new.\n\nThe product-distribution result (Theorem 2) is the bigger fish, and here I have a real problem. The paper defines a skew measure S and shows a perfect direct sum for S (Theorem 17), then relates S to D× up to O(log n). Everything hinges on Lemma 23, which claims that “the operations of applying Ext and fixing variables are commutable.” That assertion is false as stated. The stress-test gives a concrete counterexample: for k=2, n=1, a deterministic tree that queries x1 then x2, with labels (0,0) on the (0,0) leaf and (1,1) on the (0,1) leaf. If you fix both copies to 0 first, Ext_1 outputs 0 with certainty; if you fix only copy 2 and leave copy 1 as ⋆, Ext_1 outputs 0 or 1 with probability 1/2, and pruning by ρ_1=0 doesn’t change that. So the two processes are different as randomised trees.\n\nThe real question is whether the expected costs still match. The stress-test suggests the needed cost identity is plausible—pruning deletes exactly the pure copy-i queries whose coordinates are fixed—but the paper doesn’t prove it, and the false commutation claim is not a valid substitute. As written, Lemma 23 is unproved, and Theorem 17 is the load-bearing wall for Theorem 2. This is more than a minor gap: the proof of the paper’s headline product-distribution result currently has a hole.\n\nThat said, the paper is not a throwaway. The discrepancy half stands on its own, and the skew measure, the two-way inequality between S and D×, and the separations (disc vs D×, S vs D×) are all interesting and carefully done. The reliance on the folklore FFO protocol is fine. No signs of circularity or constant-fitting.\n\nWho gets value: anyone working on parity decision trees, lifting theorems, or direct sum questions in query/communication models. It deserves a serious referee, but the referee should insist on a correct proof of the cost identity in Lemma 23 (or a different argument for Theorem 17). If the authors repair that, the paper is likely acceptable; as it stands, it’s conditional at best.\n\nMy recommendation: send it to peer review, but flag the gap clearly.","headline":"First direct sum theorems for randomised parity decision trees, but the product-distribution half rests on a false commutation claim; the discrepancy half is clean.","tokens_in":36921,"tokens_out":5073,"would_cite":true,"duration_ms":49948,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves the first direct sum theorems for randomized parity decision trees: $R(f^k) \\ge \\Omega(k)\\cdot\\mathrm{disc}(f)$ for every function $f$, and $R(f^k) \\ge \\Omega(k/\\log n)\\cdot D^\\times(f)$ for every $n$-bit function $f$.","keywords":["parity decision trees","direct sum theorem","randomized query complexity","discrepancy method","product distributions","skew complexity","Fourier analysis","XOR lemma"],"falsifier":"Search by brute force over small $n$ and $k$ for a deterministic parity tree $T$ and a partial fixing $\\rho$ with $\\sum_i q(\\mathrm{Ext}_i(T_\\rho), U_{\\rho_i}) > q(T_\\rho, U_\\rho)$; any such example would falsify Lemma 23 and the perfect direct sum $S_\\varepsilon(f^k,\\mu^k)\\ge k S_\\varepsilon(f,\\mu)$. A second-looking check is whether the inequality $S_\\varepsilon(f^2,\\mu^2)\\ge 2S_\\varepsilon(f,\\mu)$ holds for every product $\\mu$ and every small explicitly enumerated $f$.","tokens_in":35792,"feed_emoji":"🌳","tokens_out":8217,"duration_ms":73683,"temperature":0.7,"pith_summary":"The paper establishes the first direct sum theorems for randomized parity decision trees: solving $k$ independent copies of a function $f$ costs at least $\\Omega(k)$ times the cost of solving one copy, for two broad classes of lower-bound techniques. The first theorem, $R(f^k) \\ge \\Omega(k)\\cdot\\mathrm{disc}(f)$, covers every function whose hardness is certified by the discrepancy method. The second, $R(f^k) \\ge \\Omega(k/\\log n)\\cdot D^\\times(f)$, covers lower bounds proved against product distributions, losing only a logarithmic factor. The proofs go through a new measure called skew complexity, which obeys a perfect direct sum and is within an $O(\\log n)$ factor of distributional parity-tree complexity.","feed_headline":"Direct sum holds for randomized parity decision trees","feed_subtitle":"Discrepancy and product-distribution lower bounds amplify linearly with k; product case loses a log factor.","key_machinery":"The central object is the skew complexity measure $S_\\varepsilon(f,\\mu)$, defined for product distributions by a two-step sampling trick: each biased bit is drawn by first sampling a random partial fixing $\\rho$ that sets the bit to 0 with probability $1-\\delta_i$ and leaves it free with probability $\\delta_i$, then drawing uniformly from the unfixed bits. $S_\\varepsilon$ is the minimal expected depth of a parity tree after this random pruning. The proof machinery also includes an extraction algorithm $\\mathrm{Ext}_i(T)$ that, given a $k$-instance tree, simulates a single copy by substituting internal randomness for the other copies, plus a Fourier characterization of discrepancy showing that max bias is within a factor of 2 of the max Fourier coefficient. The skew measure carries the argument because it has a perfect direct sum and is within an $O(\\log n)$ factor of the product-distribution measure $D^\\times$.","core_discovery":"On the paper's own terms, the central claim is that randomized parity decision tree complexity amplifies under direct sums whenever the single-copy lower bound comes from discrepancy or from a product distribution. Concretely, Theorem 1 proves $R(f^k) \\ge \\Omega(k)\\cdot\\mathrm{disc}(f)$ for every boolean function $f$, using an XOR lemma for discrepancy obtained by characterizing parity discrepancy as the maximum Fourier coefficient of $(-1)^f\\mu$ up to a factor of 2 and then observing that Fourier coefficients multiply under tensor products. Theorem 2 proves $R(f^k) \\ge \\Omega(k/\\log n)\\cdot D^\\times(f)$ for every $n$-bit $f$, via the skew measure $S_\\varepsilon$, which satisfies the perfect direct sum $S_\\varepsilon(f^k,\\mu^k)\\ge k\\cdot S_\\varepsilon(f,\\mu)$ and is related to distributional complexity by $O(\\log(n/\\gamma))$-factor conversions in both directions.","pith_inferences":["The same Fourier multiplication argument that proves the discrepancy XOR lemma could presumably yield direct sum theorems for distributional discrepancy against any tensor-product input distribution, not only the product measures used here.","The random-partial-fixing decomposition behind the skew measure may transfer to other query models with biased inputs, such as communication protocols with product distributions, where it could supply a unified explanation of the logarithmic losses seen there.","A concrete testable consequence is that the logarithmic loss in Theorem 2 is an artifact of the conversion: for any fixed function family, the actual gap between $S_\\varepsilon(f^k,\\mu^k)/k$ and $D_\\varepsilon(f,\\mu)$ should be small.","Because the perfect direct sum for $S_\\varepsilon$ is the only place where a failure could break the product-distribution result, it would be worth extracting a standalone lemma separating the commutation claim from the rest of the proof."],"forward_implications":["For any function $f$ with $R(f)=\\Theta(\\mathrm{disc}(f))$, Theorem 1 gives $R(f^k)\\ge \\Omega(k)R(f)$, resolving the direct sum question for that function.","For the uniform distribution, or more generally any bounded-bias product distribution, the direct sum is lossless up to constants: $D_\\varepsilon(f^k,\\mu^k)\\ge \\Omega(k\\lambda)D_\\varepsilon(f,\\mu)$ for $\\lambda$-bounded $\\mu$, with no logarithmic factor.","The two main theorems are incomparable: there are functions where discrepancy gives a strong $k$-fold lower bound and product distributions give none, and vice versa.","For deterministic parity trees, the paper obtains $D(f^k)\\ge k\\sqrt{D(f)}$ and $D(f^k)\\ge kD(f)/\\log \\mathrm{spar}(f)$, leaving a perfect deterministic direct sum open."],"supporting_citations":[{"why":"Supplies the minimax principle that converts randomized parity-tree lower bounds into distributional lower bounds, the starting point for Theorem 2.","marker":"[Yao77]"},{"why":"Introduces the discrepancy method for randomized lower bounds that the paper adapts to parity trees and proves a direct sum for.","marker":"[BFS86]"},{"why":"Gives the optimal direct sum theorem for ordinary randomized decision trees, the model this work extends to parity queries.","marker":"[JKS10]"},{"why":"Provides the near-optimal distributional direct sum for product distributions in communication complexity that Theorem 2 mirrors.","marker":"[BBCR13]"},{"why":"Proves a direct product theorem for discrepancy in communication complexity, the analogue of the paper's Theorem 1.","marker":"[Sha03, LSv08]"},{"why":"Supplies the parity certificate complexity bound $C(f)\\ge D(f)^{1/2}$ used in the deterministic direct sum results.","marker":"[ZS10]"},{"why":"Supplies the bound $C(f)\\ge D(f)/\\log \\mathrm{spar}(f)$ used in the second deterministic direct sum result.","marker":"[TWXZ13]"},{"why":"Gives the lower bound $D^\\times(\\mathrm{MAJ}_n)=\\Omega(n)$ used to separate discrepancy and product-distribution complexity.","marker":"[BGPW15]"},{"why":"Provides the efficient first-one search routine that the conversion from skew complexity to ordinary distributional complexity relies on.","marker":"[HR24]"}],"fun_headline_variants":["Direct sum theorem for randomized parity trees","Parity decision trees: direct sum via discrepancy","Amplify parity lower bounds with direct sums","Randomized parity trees: direct sum for two lower-bound classes","Direct sums boost parity decision tree lower bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the unproved commutation assertion in Lemma 23 that extracting a single-copy tree and fixing variables commute, which is what bounds the sum of the extracted skew costs by the original $k$-instance skew cost; if that fails, the perfect direct sum for the skew measure collapses.","fun_headline_variants_meta":{"raw":{"variants":["Direct sum theorem for randomized parity trees","Parity decision trees: direct sum via discrepancy","Amplify parity lower bounds with direct sums","Randomized parity trees: direct sum for two lower-bound classes","Direct sums boost parity decision tree lower bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000645,"raw_usage":{"total_tokens":2887,"prompt_tokens":791,"completion_tokens":2096,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":407,"completion_tokens_details":{"reasoning_tokens":2025}},"tokens_in":407,"tokens_out":2096,"duration_ms":14668,"temperature":1.0,"reasoning_tokens":2025,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:32:21.272597+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search by brute force over small $n$ and $k$ for a deterministic parity tree $T$ and a partial fixing $\\rho$ with $\\sum_i q(\\mathrm{Ext}_i(T_\\rho), U_{\\rho_i}) > q(T_\\rho, U_\\rho)$; any such example would falsify Lemma 23 and the perfect direct sum $S_\\varepsilon(f^k,\\mu^k)\\ge k S_\\varepsilon(f,\\mu)$. A second-looking check is whether the inequality $S_\\varepsilon(f^2,\\mu^2)\\ge 2S_\\varepsilon(f,\\mu)$ holds for every product $\\mu$ and every small explicitly enumerated $f$.","supporting_citations":[],"review_version":1}