{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T12:20:31Z","timestamp":1777983631853,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T00:00:00Z","timestamp":1777939200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T00:00:00Z","timestamp":1777939200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00037-026-00285-y","type":"journal-article","created":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T11:37:32Z","timestamp":1777981052000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A strong direct sum theorem for distributional query complexity"],"prefix":"10.1007","volume":"35","author":[{"given":"Guy","family":"Blanc","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Caleb","family":"Koch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmen","family":"Strassle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,5]]},"reference":[{"key":"285_CR1","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Lo\u00efck Magnin, Martin Roetteler & J\u00e9r\u00e9mie Roland (2011). Symmetry-assisted adversaries for quantum state generation. In 2011 IEEE 26th Annual Conference on Computational Complexity (CCC), 167\u2013177. IEEE.","DOI":"10.1109\/CCC.2011.24"},{"key":"285_CR2","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Robert \u0160palek & Ronald de\u00a0Wolf (2006). A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 618\u2013633.","DOI":"10.1145\/1132516.1132604"},{"key":"285_CR3","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi & Vishvajeet N (2021). Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), Samir Khuller & Virginia\u00a0Vassilevska Williams, editors, 612\u2013625.","DOI":"10.1145\/3406325.3451110"},{"key":"285_CR4","doi-asserted-by":"crossref","unstructured":"Boaz Barak, Mark Braverman, Xi\u00a0Chen & Anup Rao (2010). How to compress interactive communication. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 67\u201376.","DOI":"10.1145\/1806689.1806701"},{"key":"285_CR5","doi-asserted-by":"crossref","unstructured":"Shalev Ben-David & Robin Kothari (2018). Randomized Query Complexity of Sabotaged and Composed Functions. Theory of Computing 14(5), 1\u201327. https:\/\/theoryofcomputing.org\/articles\/v014a005.","DOI":"10.4086\/toc.2018.v014a005"},{"key":"285_CR6","unstructured":"Eric Blais & Joshua Brody (2019). Optimal Separation and Strong Direct Sum for Randomized Query Complexity. In 34th Computational Complexity Conference (CCC), volume 137, 29:1\u201329:17. ISBN 978-3-95977-116-0. ISSN 1868-8969. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10851."},{"key":"285_CR7","doi-asserted-by":"crossref","unstructured":"Guy Blanc, Caleb Koch, Carmen Strassle & Li-Yang Tan (2023). A strong composition theorem for junta complexity and the boosting of property testers. In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), 1757\u20131777.","DOI":"10.1109\/FOCS57990.2023.00107"},{"key":"285_CR8","unstructured":"Guy Blanc, Caleb Koch, Carmen Strassle & Li-Yang Tan (2024). A Strong Direct Sum Theorem for Distributional Query Complexity. In 39th Computational Complexity Conference (CCC 2024), 16\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"285_CR9","doi-asserted-by":"crossref","unstructured":"Mark Braverman, Anup Rao, Omri Weinstein & Amir Yehudayoff (2013). Direct products in communication complexity. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), 746\u2013755.","DOI":"10.1109\/FOCS.2013.85"},{"key":"285_CR10","doi-asserted-by":"crossref","unstructured":"Joshua Brody, Jae\u00a0Tak Kim, Peem Lerdputtipongporn & Hariharan Srinivasulu (2023). A Strong XOR Lemma for Randomized Query Complexity. Theory of Computing 19(11), 1\u201314. https:\/\/theoryofcomputing.org\/articles\/v019a011.","DOI":"10.4086\/toc.2023.v019a011"},{"key":"285_CR11","doi-asserted-by":"crossref","unstructured":"Andrew Drucker (2012). Improved direct product theorems for randomized query complexity. computational complexity 21(2), 197\u2013244.","DOI":"10.1007\/s00037-012-0043-7"},{"key":"285_CR12","doi-asserted-by":"crossref","unstructured":"Andrew Drucker (2013). Nondeterministic direct product reductions and the success probability of SAT solvers. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), 736\u2013745.","DOI":"10.1109\/FOCS.2013.84"},{"key":"285_CR13","first-page":"273","volume":"6650","author":"Oded Goldreich","year":"2011","unstructured":"Oded Goldreich, Noam Nisan & Avi Wigderson (2011). On Yao\u2019s XOR-Lemma. Studies in Complexity and Cryptography 6650, 273\u2013301.","journal-title":"Studies in Complexity and Cryptography"},{"key":"285_CR14","unstructured":"William Hoza (2023). A Technique for Hardness Amplification Against AC0. ECCC preprint TR23-176 ."},{"key":"285_CR15","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (1995). Hard-core distributions for somewhat hard problems. In Proceedings of IEEE 36th Annual Foundations of Computer Science (FOCS), 538\u2013545.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"285_CR16","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets & Avi Wigderson (2008). Uniform direct product theorems: simplified, optimized, and derandomized. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 579\u2013588.","DOI":"10.1145\/1374376.1374460"},{"key":"285_CR17","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Ran Raz & Avi Wigderson (1994). A direct product theorem. In Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory, 88\u201396.","DOI":"10.1109\/SCT.1994.315814"},{"key":"285_CR18","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). $${{\\rm P}}={{\\rm BPP}}$$ if $${{\\rm E}}$$ requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), 220\u2013229.","DOI":"10.1145\/258533.258590"},{"issue":"3","key":"285_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2699432","volume":"62","author":"Rahul Jain","year":"2015","unstructured":"Rahul Jain (2015). New strong direct product results in communication complexity. Journal of the ACM (JACM) 62(3), 1\u201327.","journal-title":"Journal of the ACM (JACM)"},{"issue":"20","key":"285_CR20","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1016\/j.ipl.2010.07.020","volume":"110","author":"Rahul Jain","year":"2010","unstructured":"Rahul Jain, Hartmut Klauck & Miklos Santha (2010). Optimal direct sum results for deterministic and randomized decision tree complexity. Information Processing Letters 110(20), 893\u2013897.","journal-title":"Information Processing Letters"},{"key":"285_CR21","doi-asserted-by":"crossref","unstructured":"Rahul Jain, Attila Pereszl\u00e9nyi & Penghui Yao (2012). A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), 167\u2013176.","DOI":"10.1109\/FOCS.2012.42"},{"key":"285_CR22","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2010). A strong direct product theorem for disjointness. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 77\u201386.","DOI":"10.1145\/1806689.1806702"},{"key":"285_CR23","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck, Robert \u0160palek & Ronald de\u00a0Wolf (2007). Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM Journal on Computing 36(5), 1472\u20131493. Preliminary version in FOCS 2004.","DOI":"10.1137\/05063235X"},{"key":"285_CR24","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1022949332276","volume":"51","author":"Adam R Klivans","year":"2003","unstructured":"Adam\u00a0R Klivans & Rocco\u00a0A Servedio (2003). Boosting and hard-core set construction. Machine Learning 51, 217\u2013238.","journal-title":"Machine Learning"},{"key":"285_CR25","doi-asserted-by":"crossref","unstructured":"Troy Lee & J\u00e9r\u00e9mie Roland (2013). A strong direct product theorem for quantum query complexity. computational complexity 22, 429\u2013462.","DOI":"10.1007\/s00037-013-0066-8"},{"key":"285_CR26","doi-asserted-by":"crossref","unstructured":"Troy Lee, Adi Shraibman & Robert \u0160palek (2008). A direct product theorem for discrepancy. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (CCC), 71\u201380.","DOI":"10.1109\/CCC.2008.25"},{"key":"285_CR27","doi-asserted-by":"crossref","unstructured":"Leonid\u00a0A Levin (1985). One-way functions and pseudorandom generators. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), 363\u2013365.","DOI":"10.1145\/22145.22185"},{"key":"285_CR28","doi-asserted-by":"crossref","unstructured":"Noam Nisan, Steven Rudich & Michael Saks (1994). Products and help bits in decision trees. In Proceedings 35th Annual Symposium on Foundations of Computer Science (FOCS), 318\u2013329.","DOI":"10.1109\/SFCS.1994.365683"},{"issue":"2","key":"285_CR29","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Noam Nisan & Avi Wigderson","year":"1994","unstructured":"Noam Nisan & Avi Wigderson (1994). Hardness vs randomness. Journal of computer and System Sciences 49(2), 149\u2013167.","journal-title":"Journal of computer and System Sciences"},{"key":"285_CR30","doi-asserted-by":"crossref","unstructured":"Ryan O\u2019Donnell (2002). Hardness amplification within NP. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 751\u2013760.","DOI":"10.1145\/509907.510015"},{"issue":"1\/2","key":"285_CR31","first-page":"1","volume":"12","author":"Ronen Shaltiel","year":"2004","unstructured":"Ronen Shaltiel (2004). Towards proving strong direct product theorems. Computational Complexity 12(1\/2), 1\u201322.","journal-title":"Computational Complexity"},{"key":"285_CR32","doi-asserted-by":"crossref","unstructured":"Alexander\u00a0A Sherstov (2011). Strong direct product theorems for quantum communication and query complexity. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 41\u201350.","DOI":"10.1145\/1993636.1993643"},{"key":"285_CR33","doi-asserted-by":"crossref","unstructured":"Robert \u0160palek (2008). The multiplicative quantum adversary. In 23rd Annual IEEE Conference on Computational Complexity (CCC), 237\u2013248.","DOI":"10.1109\/CCC.2008.9"},{"key":"285_CR34","first-page":"184","volume":"264","author":"Volker Strassen","year":"1973","unstructured":"Volker Strassen (1973). Vermeidung von divisionen. Journal f\u00fcr die reine und angewandte Mathematik 264, 184\u2013202.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"285_CR35","unstructured":"Luca Trevisan (2007). The Impagliazzo Hard-Core-Set Theorem. https:\/\/lucatrevisan.wordpress.com\/2007\/11\/06\/the-impagliazzo-hard-core-set-theorem\/."},{"key":"285_CR36","doi-asserted-by":"crossref","unstructured":"Emanuele Viola & Avi Wigderson (2008). Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1), 137\u2013168.","DOI":"10.4086\/toc.2008.v004a007"},{"key":"285_CR37","doi-asserted-by":"crossref","unstructured":"Andrew Yao (1982). Theory and application of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), 80\u201391.","DOI":"10.1109\/SFCS.1982.45"},{"key":"285_CR38","doi-asserted-by":"crossref","unstructured":"Huacheng Yu (2022). Strong XOR Lemma for Communication with Bounded Rounds. In Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS), 1186\u20131192.","DOI":"10.1109\/FOCS54457.2022.00114"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-026-00285-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-026-00285-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-026-00285-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T11:38:02Z","timestamp":1777981082000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-026-00285-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,5]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["285"],"URL":"https:\/\/doi.org\/10.1007\/s00037-026-00285-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,5]]},"assertion":[{"value":"24 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}