2026-07-20T07:34:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23710 2025-10-27T10:42:41Z ddc:004 open_access

Direct Sums for Parity Decision Trees Besselman, Tyler Göös, Mika Guo, Siyao Maystre, Gilbert Yuan, Weiqiang direct sum parity decision trees query complexity Direct sum theorems state that the cost of solving k instances of a problem is at least Ω(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tyler Besselman and Mika Göös and Siyao Guo and Gilbert Maystre and Weiqiang Yuan 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.16 urn:nbn:de:0030-drops-237105 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode