Direct Sums for Parity Decision Trees

Gilbert Maystre; Mika G\"o\"os; Siyao Guo; Tyler Besselman; Weiqiang Yuan

REVIEW 1 major objections 4 minor 57 references

Direct Sums for Parity Decision Trees

T0 review · 1 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read 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$.

desk verdict 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. read the letter →

arxiv 2412.06552 v2 pith:5VA5HSPN submitted 2024-12-09 cs.CC

Tyler Besselman , Mika Göös , Siyao Guo , Gilbert Maystre , Weiqiang Yuan This is my paper · ORCID

classification cs.CC MSC 68Q1768Q25

keywords paritydecisiontreesdirectsumtheoremrandomizedquerycomplexitydiscrepancymethodproductdistributionsskewFourieranalysisXORlemma

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

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.

What carries the argument

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$.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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.

Desk Editor's Note

read the letter

Colleague,

This 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.

The 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.

The 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.

That 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.

Who 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.

My recommendation: send it to peer review, but flag the gap clearly.

Referee Report

1 major / 4 minor

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.

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 (1)

[§5.2, Lemma 23] 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.

minor comments (4)

[§A.4, Claim 10] 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.
[§6, Lemma 25, last case] 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}.
[§6.2, Lemma 31 and Theorem 18] 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/γ)).
[Appendix A.4, Lemma 29] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the direct sum results derive from first-principles Fourier and extraction arguments; the load-bearing Lemma 23 gap is a correctness issue, not a circular reduction.

full rationale

The paper's central engine is the skew measure S_ε(f,µ), defined independently via random partial fixings; its perfect direct sum (Theorem 17) is proved by an extraction algorithm, with Claim 21 providing a simulation identity. The two-way inequalities between S and D_ε (Theorems 18 and 19) are proved by explicit conversion algorithms, and the discrepancy results use a Fourier characterisation and tensor product. No parameter is fitted to the target, no target quantity appears in the definition of the new measure, and no load-bearing claim is justified solely by author self-citation. The only concern is Lemma 23's third equality ('the operations of applying Ext and fixing variables are commutable'), which is asserted without proof and appears to be false in general; however an unproved or false step is a correctness gap, not circularity. Hence score 0.

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

The paper's central claims rest only on standard mathematical tools (Fourier analysis, linear algebra, Yao's principle) and two cited folklore/prior results (FFO protocol, certificate complexity bounds). No free parameters are fit to data; the main new construct is the skew measure, a formal device rather than a physical postulate.

assumptions (4)

standard math Fourier inversion and Parseval identities over {0,1}^n
Used throughout Section 3, e.g., Lemma 8 and Claim 9, to characterize discrepancy via the L∞ norm of the Fourier transform.
domain assumption Yao's minimax principle for randomized parity decision trees
Invoked to relate worst-case randomized complexity R to distributional complexity D (Lemma 40), a standard theorem in computational complexity.
domain assumption Folklore result: the 'first one' problem FFO_n can be solved by a randomized parity decision tree with O(log n) queries and small error (Lemma 29)
Essential for the conversion from skew complexity to standard distributional complexity in Theorem 18 and Algorithm 5; the paper cites [FPRU90, Nis93, HR24] and does not give a full self-contained proof.
domain assumption Certificate complexity bounds C(f) ≥ D(f)^{1/2} (ZS10) and C(f) ≥ D(f)/log spar(f) (TWXZ13)
Used in Theorem 4 (deterministic direct sum results) to lift a direct sum for certificate complexity to decision tree depth; taken from prior work.

invented entities (1)

Skew complexity measure S_ε(f, µ)
purpose: A new complexity measure tailored to product distributions; it splits each biased bit into a random fixing and a uniform bit, and it satisfies a perfect direct sum theorem. It is the main technical device for proving Theorem 2.
The measure is a formal mathematical construct with no external falsifiable handle; its value is justified by the internal theorems proving a perfect direct sum and a two-sided approximation to D×.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Direct Sums for Parity Decision Trees." pith.science (2026). https://pith.science/paper/5VA5HSPN

@misc{pith2026241206552,
  author       = {Pith},
  title        = {Pith review of: Direct Sums for Parity Decision Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5VA5HSPN}},
  note         = {Machine review of arXiv:2412.06552}
}

abstract

Direct sum theorems state that the cost of solving $k$ instances of a problem is at least $\Omega(k)$ times the cost of solving a single instance. We prove the first such results in the randomised parity decision tree model. We show that a direct sum theorem holds whenever (1) the lower bound for parity decision trees is proved using the discrepancy method; or (2) the lower bound is proved relative to a product distribution.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 30 canonical work pages

[1]

Lifting Dichotomies

Yaroslav Alekseev, Yuval Filmus, and Alexander Smal. Lifting Dichotomies . In 39th Computational Complexity Conference (CCC 2024) , volume 300 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 9:1--9:18. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2024. https://doi.org/10.4230/LIPIcs.CCC.2024.9 doi:10.4230/LIPIcs.CCC.2024.9

doi:10.4230/lipics.ccc.2024.9 2024
[2]

Lifting to bounded-depth and regular resolutions over parities via games

Yaroslav Alekseev and Dmitry Itsykson. Lifting to bounded-depth and regular resolutions over parities via games. Technical Report TR24-128, ECCC, 2024. URL: https://eccc.weizmann.ac.il/report/2024/128/

work page 2024
[3]

Optimal separation and strong direct sum for randomized query complexity

Eric Blais and Joshua Brody. Optimal separation and strong direct sum for randomized query complexity. In Proceedings of the 34th Computational Complexity Conference , CCC '19. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. https://doi.org/10.4230/LIPIcs.CCC.2019.29 doi:10.4230/LIPIcs.CCC.2019.29

doi:10.4230/lipics.ccc.2019.29 2019
[4]

A tight composition theorem for the randomized query complexity of partial functions: Extended abstract

Shalev Ben - David and Eric Blais. A tight composition theorem for the randomized query complexity of partial functions: Extended abstract. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 240--246, 2020. https://doi.org/10.1109/FOCS46700.2020.00031 doi:10.1109/FOCS46700.2020.00031

arXiv 2020
[5]

A new minimax theorem for randomized algorithms

Shalev Ben - David and Eric Blais. A new minimax theorem for randomized algorithms. J. ACM , 70(6), 2023. https://doi.org/10.1145/3626514 doi:10.1145/3626514

work page doi:10.1145/3626514 2023
[6]

How to compress interactive communication

Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM Journal on Computing , 42(3):1327--1363, 2013. https://doi.org/10.1137/100811969 doi:10.1137/100811969

work page doi:10.1137/100811969 2013
[7]

Randomised Composition and Small-Bias Minimax

Shalev Ben - David, Eric Blais, Mika G\"o\"os, and Gilbert Maystre. Randomised Composition and Small-Bias Minimax . In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 624--635. IEEE Computer Society, 2022. https://doi.org/10.1109/FOCS54457.2022.00065 doi:10.1109/FOCS54457.2022.00065

arXiv 2022
[8]

Exponential Separation Between Powers of Regular and General Resolution over Parities

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, and Pavel Dvo r \' a k. Exponential Separation Between Powers of Regular and General Resolution over Parities . In 39th Computational Complexity Conference (CCC 2024) , volume 300 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 23:1--23:32. Schloss Dagstuhl -- Leibniz-Zentrum f \"u ...

work page doi:10.4230/lipics.ccc.2024.23 2024

Show all 57 references

[9]

Complexity classes in communication complexity theory

Laszlo Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) , pages 337--347, 1986. https://doi.org/10.1109/SFCS.1986.15 doi:10.1109/SFCS.1986.15

1986 doi
[10]

When Is Amplification Necessary for Composition in Randomized Query Complexity? In Approximation, Randomization, and Combinatorial Optimization

Shalev Ben - David, Mika G\" o \" o s, Robin Kothari, and Thomas Watson. When Is Amplification Necessary for Composition in Randomized Query Complexity? In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) , volume 176...

2020 doi
[11]

Information lower bounds via self-reducibility

Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. Information lower bounds via self-reducibility. Theory of Computing Systems , 59(2):377--396, 2015. https://doi.org/10.1007/s00224-015-9655-z doi:10.1007/s00224-015-9655-z

2015 doi
[12]

Lifting to randomized parity decision trees

Farzan Byramji and Russell Impagliazzo. Lifting to randomized parity decision trees. Technical Report TR24-202, ECCC, 2024. URL: https://eccc.weizmann.ac.il/report/2024/202/

2024
[13]

Randomized query complexity of sabotaged and composed functions

Shalev Ben - David and Robin Kothari. Randomized query complexity of sabotaged and composed functions. Theory of Computing , 14(5):1--27, 2018. https://doi.org/10.4086/toc.2018.v014a005 doi:10.4086/toc.2018.v014a005

2018 doi
[14]

On Disperser/Lifting Properties of the Index and Inner-Product Functions

Paul Beame and Sajin Koroth. On Disperser/Lifting Properties of the Index and Inner-Product Functions . In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 14:1--14:17. Sch...

2023 doi
[15]

A strong XOR lemma for randomized query complexity

Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu. A strong XOR lemma for randomized query complexity. Theory of Computing , 19(11):1--14, 2023. https://doi.org/10.4086/toc.2023.v019a011 doi:10.4086/toc.2023.v019a011

2023 doi
[16]

A Strong Direct Sum Theorem for Distributional Query Complexity

Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan. A Strong Direct Sum Theorem for Distributional Query Complexity . In 39th Computational Complexity Conference (CCC 2024) , volume 300 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 16:1--16:30. Schl...

2024 doi
[17]

Information equals amortized communication

Mark Braverman and Anup Rao. Information equals amortized communication. IEEE Transactions on Information Theory , 60(10):6058--6069, 2014. https://doi.org/10.1109/TIT.2014.2347282 doi:10.1109/TIT.2014.2347282

2014
[18]

Super-critical trade-offs in resolution over parities via lifting

Arkadev Chattopadhyay and Pavel Dvorak. Super-critical trade-offs in resolution over parities via lifting. Technical Report TR24-132, ECCC, 2024. URL: https://eccc.weizmann.ac.il/report/2024/132/

2024
[19]

Boolean functions with small approximate spectral norm

Tsun Ming Cheung, Hamed Hatami, Rosie Zhao, and Itai Zilberstein. Boolean functions with small approximate spectral norm. Discrete Analysis , 2024. https://doi.org/10.19086/da.122971 doi:10.19086/da.122971

2024 doi
[20]

Lifting to Parity Decision Trees via Stifling

Arkadev Chattopadhyay, Nikhil Mande, Swagato Sanyal, and Suhail Sherif. Lifting to Parity Decision Trees via Stifling . In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz International Proceedings in Informatics (LIPIcs) , pages ...

2023 doi
[21]

Improved direct product theorems for randomized query complexity

Andrew Drucker. Improved direct product theorems for randomized query complexity. Comput. Complex. , 21(2):197–244, 2012. https://doi.org/10.1007/s00037-012-0043-7 doi:10.1007/s00037-012-0043-7

2012 doi
[22]

Lower bounds for regular resolution over parities

Klim Efremenko, Michal Garlík, and Dmitry Itsykson. Lower bounds for regular resolution over parities. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , volume 41 of STOC ’24 , pages 640--651. ACM, 2024. https://doi.org/10.1145/3618260.3649652 doi:10.114...

2024
[23]

Proving Unsatisfiability with Hitting Formulas

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, and Marc Vinyals. Proving Unsatisfiability with Hitting Formulas . In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , volume 287 of Leibniz International Proceedings in Informatics (LIPIcs) ...

2024 doi
[24]

Amortized communication complexity

Tom\' a s Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan. Amortized communication complexity. SIAM Journal on Computing , 24(4):736--750, 1995. https://doi.org/10.1137/S0097539792235864 doi:10.1137/S0097539792235864

1995 doi
[25]

Feige, D

U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Computing with unreliable information. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing , STOC '90, page 128–137. Association for Computing Machinery, 1990. https://doi.org/10.1145/100216.100230 doi:...

1990
[26]

Exponential separation of information and communication for boolean functions

Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of information and communication for boolean functions. J. ACM , 63(5), 2016. https://doi.org/10.1145/2907939 doi:10.1145/2907939

2016 doi
[27]

A majority lemma for randomised query complexity

Mika G\" o \" o s and Gilbert Maystre. A majority lemma for randomised query complexity. In Proceedings of the 36th Computational Complexity Conference , CCC '21. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021. https://doi.org/10.4230/LIPIcs.CCC.2021.18 doi:10.4230/LI...

2021 doi
[28]

Fourier growth of communication protocols for XOR functions

Uma Girish, Makrand Sinha, Avishay Tal, and Kewen Wu. Fourier growth of communication protocols for XOR functions. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 721--732, 2023. https://doi.org/10.1109/FOCS57990.2023.00047 doi:10.1109/FOCS...

2023
[29]

Fourier growth of parity decision trees

Uma Girish, Avishay Tal, and Kewen Wu. Fourier growth of parity decision trees. In Proceedings of the 36th Computational Complexity Conference , CCC '21. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021. https://doi.org/10.4230/LIPIcs.CCC.2021.39 doi:10.4230/LIPIcs.CCC.2021.39

2021 doi
[30]

Structure of protocols for XOR functions

Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for XOR functions. SIAM Journal on Computing , 47(1):208--217, 2018. https://doi.org/10.1137/17M1136869 doi:10.1137/17M1136869

2018 doi
[31]

Refuting Approaches to the Log-Rank Conjecture for XOR Functions

Hamed Hatami, Kaave Hosseini, Shachar Lovett, and Anthony Ostuni. Refuting Approaches to the Log-Rank Conjecture for XOR Functions . In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , volume 297 of Leibniz International Proceedings in Infor...

2024 doi
[32]

Better Boosting of Communication Oracles, or Not

Nathaniel Harms and Artur Riazanov. Better Boosting of Communication Oracles, or Not . In Siddharth Barman and S awomir Lasota, editors, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024) , volume 323 of Leibniz In...

2024 doi
[33]

An XOR lemma for deterministic communication complexity, 2024

Siddharth Iyer and Anup Rao. An XOR lemma for deterministic communication complexity, 2024. URL: https://arxiv.org/abs/2407.01802

2024 arXiv
[34]

XOR lemmas for communication via marginal information

Siddharth Iyer and Anup Rao. XOR lemmas for communication via marginal information. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, pages 652--–658. Association for Computing Machinery, 2024. https://doi.org/10.1145/3618260.3649726 doi:10.11...

2024
[35]

Resolution over linear equations modulo two

Dmitry Itsykson and Dmitry Sokolov. Resolution over linear equations modulo two. Annals of Pure and Applied Logic , 171(1):102722, 2020. https://doi.org/10.1016/j.apal.2019.102722 doi:10.1016/j.apal.2019.102722

2020
[36]

Optimal direct sum results for deterministic and randomized decision tree complexity

Rahul Jain, Hartmut Klauck, and Miklos Santha. Optimal direct sum results for deterministic and randomized decision tree complexity. Information Processing Letters , 110(20):893--897, 2010. https://doi.org/10.1016/j.ipl.2010.07.020 doi:10.1016/j.ipl.2010.07.020

2010 doi
[37]

A direct sum theorem in communication complexity via message compression

Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A direct sum theorem in communication complexity via message compression. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming , pages 300--315. Spring...

2003 doi
[38]

A. Knop, S. Lovett, S. McGuire, and W. Yuan. Guest column: Models of computation between decision trees and communication. SIGACT News , 52(2):46–70, 2021. https://doi.org/10.1145/3471469.3471479 doi:10.1145/3471469.3471479

2021
[39]

Learning decision trees using the fourier spectrum

Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM Journal on Computing , 22(6):1331--1348, 1993. https://doi.org/10.1137/0222080 doi:10.1137/0222080

1993 doi
[40]

Quantum and classical strong direct product theorems and optimal time‐space tradeoffs

Hartmut Klauck, Robert S palek, and Ronald de Wolf. Quantum and classical strong direct product theorems and optimal time‐space tradeoffs. SIAM Journal on Computing , 36(5):1472--1493, 2007. https://doi.org/10.1137/05063235X doi:10.1137/05063235X

2007 doi
[41]

Learning complexity vs

Nati Linial and Adi Shraibman. Learning complexity vs. communication complexity. In 2008 23rd Annual IEEE Conference on Computational Complexity , pages 53--63, 2008. https://doi.org/10.1109/CCC.2008.28 doi:10.1109/CCC.2008.28

2008 doi
[42]

A direct product theorem for discrepancy

Troy Lee, Adi Shraibman, and Robert S palek. A direct product theorem for discrepancy. In 2008 23rd Annual IEEE Conference on Computational Complexity , pages 71--80, 2008. https://doi.org/10.1109/CCC.2008.25 doi:10.1109/CCC.2008.25

2008 doi
[43]

On parity decision trees for fourier-sparse boolean functions

Nikhil Mande and Swagato Sanyal. On parity decision trees for fourier-sparse boolean functions. ACM Trans. Comput. Theory , 16(2), 2024. https://doi.org/10.1145/3647629 doi:10.1145/3647629

2024 doi
[44]

The communication complexity of threshold gates

Noam Nisan. The communication complexity of threshold gates. Proc. of Combinatorics, Paul Erd o s is Eighty , 1993

1993
[45]

Analysis of Boolean Functions

Ryan O'Donnell. Analysis of Boolean Functions . Cambridge University Press, 2014. https://doi.org/10.1017/CBO9781139814782 doi:10.1017/CBO9781139814782

2014 doi
[46]

A Composition Theorem for Parity Kill Number

Ryan ODonnell, John Wright, Yu Zhao, Xiaorui Sun, and Li-Yang Tan. A Composition Theorem for Parity Kill Number . In 2014 IEEE Conference on Computational Complexity (CCC) , pages 144--154. IEEE Computer Society, 2014. https://doi.org/10.1109/CCC.2014.22 doi:10.1109/CCC.2014.22

2014 doi
[47]

Simplified separation of information and communication

Anup Rao and Makrand Sinha. Simplified separation of information and communication. Theory of Computing , 14(20):1--29, 2018. https://doi.org/10.4086/toc.2018.v014a020 doi:10.4086/toc.2018.v014a020

2018 doi
[48]

Fourier sparsity and dimension

Swagato Sanyal. Fourier sparsity and dimension. Theory of Computing , 15(11):1--13, 2019. https://doi.org/10.4086/toc.2019.v015a011 doi:10.4086/toc.2019.v015a011

2019 doi
[49]

Randomized query composition and product distributions

Swagato Sanyal. Randomized query composition and product distributions. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS) , volume 289 of LIPIcs , pages 56:1--56:19. Schloss Dagstuhl, 2024. https://doi.org/10.4230/LIPIcs.STACS.2024.56 doi:10.42...

2024 doi
[50]

On determinism versus unambiquous nondeterminism for decision trees

Petr Savick \'y . On determinism versus unambiquous nondeterminism for decision trees. Technical Report TR02-009, Electronic Colloquium on Computational Complexity (ECCC), 2002. URL: http://eccc.hpi-web.de/report/2002/009/

2002
[51]

Towards proving strong direct product theorems

Ronen Shaltiel. Towards proving strong direct product theorems. computational complexity , 12(1):1--22, 2003. https://doi.org/10.1007/s00037-003-0175-x doi:10.1007/s00037-003-0175-x

2003 doi
[52]

Randomized lifting to semi-structured communication complexity via linear diversity

Alexander Shekhovtsov and Vladimir Podolskii. Randomized lifting to semi-structured communication complexity via linear diversity. In 16th Innovations in Theoretical Computer Science Conference (ITCS) , LIPIcs. Schloss Dagstuhl, 2025

2025
[53]

On the structure of boolean functions with small spectral norm

Amir Shpilka, Avishay Tal, and Ben Volk. On the structure of boolean functions with small spectral norm. computational complexity , 26(1):229--273, 2017. https://doi.org/doi.org/10.1007/s00037-015-0110-y doi:doi.org/10.1007/s00037-015-0110-y

2017 doi
[54]

Fourier sparsity, spectral norm, and the log-rank conjecture

Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages 658--667, 2013. https://doi.org/10.1109/FOCS.2013.76 doi:10.1109/FOCS.2013.76

2013 doi
[55]

Probabilistic computations: Toward a unified measure of complexity

Andrew Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science , SFCS '77, page 222–227. IEEE Computer Society, 1977. https://doi.org/10.1109/SFCS.1977.24 doi:10.1109/SFCS.1977.24

1977 doi
[56]

Lower bounds by probabilistic arguments

Andrew Yao. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science , SFCS '83, page 420–428. IEEE Computer Society, 1983. https://doi.org/10.1109/SFCS.1983.30 doi:10.1109/SFCS.1983.30

1983 doi
[57]

On the parity complexity measures of boolean functions

Zhiqiang Zhang and Yaoyun Shi. On the parity complexity measures of boolean functions. Theoretical Computer Science , 411(26-28):2612--2618, 2010. https://doi.org/10.1016/j.tcs.2010.03.027 doi:10.1016/j.tcs.2010.03.027

2010 doi

Pith tools

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

[1] [1]

Lifting Dichotomies

Yaroslav Alekseev, Yuval Filmus, and Alexander Smal. Lifting Dichotomies . In 39th Computational Complexity Conference (CCC 2024) , volume 300 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 9:1--9:18. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2024. https://doi.org/10.4230/LIPIcs.CCC.2024.9 doi:10.4230/LIPIcs.CCC.2024.9

doi:10.4230/lipics.ccc.2024.9 2024

[2] [2]

Lifting to bounded-depth and regular resolutions over parities via games

Yaroslav Alekseev and Dmitry Itsykson. Lifting to bounded-depth and regular resolutions over parities via games. Technical Report TR24-128, ECCC, 2024. URL: https://eccc.weizmann.ac.il/report/2024/128/

work page 2024

[3] [3]

Optimal separation and strong direct sum for randomized query complexity

Eric Blais and Joshua Brody. Optimal separation and strong direct sum for randomized query complexity. In Proceedings of the 34th Computational Complexity Conference , CCC '19. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. https://doi.org/10.4230/LIPIcs.CCC.2019.29 doi:10.4230/LIPIcs.CCC.2019.29

doi:10.4230/lipics.ccc.2019.29 2019

[4] [4]

A tight composition theorem for the randomized query complexity of partial functions: Extended abstract

Shalev Ben - David and Eric Blais. A tight composition theorem for the randomized query complexity of partial functions: Extended abstract. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 240--246, 2020. https://doi.org/10.1109/FOCS46700.2020.00031 doi:10.1109/FOCS46700.2020.00031

arXiv 2020

[5] [5]

A new minimax theorem for randomized algorithms

Shalev Ben - David and Eric Blais. A new minimax theorem for randomized algorithms. J. ACM , 70(6), 2023. https://doi.org/10.1145/3626514 doi:10.1145/3626514

work page doi:10.1145/3626514 2023

[6] [6]

How to compress interactive communication

Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. SIAM Journal on Computing , 42(3):1327--1363, 2013. https://doi.org/10.1137/100811969 doi:10.1137/100811969

work page doi:10.1137/100811969 2013

[7] [7]

Randomised Composition and Small-Bias Minimax

Shalev Ben - David, Eric Blais, Mika G\"o\"os, and Gilbert Maystre. Randomised Composition and Small-Bias Minimax . In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 624--635. IEEE Computer Society, 2022. https://doi.org/10.1109/FOCS54457.2022.00065 doi:10.1109/FOCS54457.2022.00065

arXiv 2022

[8] [8]

Exponential Separation Between Powers of Regular and General Resolution over Parities

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, and Pavel Dvo r \' a k. Exponential Separation Between Powers of Regular and General Resolution over Parities . In 39th Computational Complexity Conference (CCC 2024) , volume 300 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 23:1--23:32. Schloss Dagstuhl -- Leibniz-Zentrum f \"u ...

work page doi:10.4230/lipics.ccc.2024.23 2024