{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:17:58Z","timestamp":1759335478071},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00037-012-0043-7","type":"journal-article","created":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T04:14:48Z","timestamp":1338524088000},"page":"197-244","source":"Crossref","is-referenced-by-count":10,"title":["Improved direct product theorems for randomized query complexity"],"prefix":"10.1007","volume":"21","author":[{"given":"Andrew","family":"Drucker","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,6,2]]},"reference":[{"key":"43_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 26th IEEE Conference on Computational Complexity, 167\u2013177.","DOI":"10.1109\/CCC.2011.24"},{"issue":"3","key":"43_CR2","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/s00453-007-9022-9","volume":"55","author":"Ambainis Andris","year":"2009","unstructured":"Andris Ambainis, Robert \u0160palek, de Ronald Wolf (2009) A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 55(3): 422\u2013461 Earlier version in STOC 2006.","journal-title":"Algorithmica"},{"issue":"4","key":"43_CR3","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/s00224-006-1313-z","volume":"40","author":"Buhrman Harry","year":"2007","unstructured":"Harry Buhrman, Ilan Newman, Hein R\u00f6hrig, de Ronald Wolf (2007) Robust Polynomials and Quantum Algorithms. Theory Comput. Syst. 40(4): 379\u2013395 Earlier version in STACS 2005.","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"43_CR4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"Buhrman Harry","year":"2002","unstructured":"Harry Buhrman, de Ronald Wolf (2002) Complexity Measures and Decision Tree Complexity: a Survey. Theor. Comput. Sci. 288(1): 21\u201343","journal-title":"Theor. Comput. Sci."},{"key":"43_CR5","doi-asserted-by":"crossref","unstructured":"Devdatt P. Dubhashi & Alessandro Panconesi (2009). Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 1st edition.","DOI":"10.1017\/CBO9780511581274"},{"issue":"5","key":"43_CR6","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"Feige Uriel","year":"1994","unstructured":"Uriel Feige, Prabhakar Raghavan, David Peleg, Eli Upfal (1994) Computing with Noisy Information. SIAM J. Comput. 23(5): 1001\u20131018 Earlier version in STOC 1990.","journal-title":"SIAM J. Comput."},{"key":"43_CR7","unstructured":"Oded Goldreich, Noam Nisan & Avi Wigderson (1995). On Yao\u2019s XOR-Lemma. Electronic Colloquium on Computational Complexity (ECCC) TR95-050."},{"key":"43_CR8","doi-asserted-by":"crossref","unstructured":"Thomas Holenstein (2005). Key Agreement from Weak Bit Agreement. In 37th ACM STOC, 664\u2013673.","DOI":"10.1145\/1060590.1060689"},{"key":"43_CR9","unstructured":"Thomas Holenstein & Grant Schoenebeck (2011). General Hardness Amplification of Predicates and Puzzles - (Extended Abstract). In TCC, 19\u201336."},{"key":"43_CR10","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (1995). Hard-Core Distributions for Somewhat Hard Problems. In 36th IEEE FOCS, 538\u2013545.","DOI":"10.1109\/SFCS.1995.492584"},{"issue":"4","key":"43_CR11","doi-asserted-by":"crossref","first-page":"1637","DOI":"10.1137\/080734030","volume":"39","author":"Impagliazzo Russell","year":"2010","unstructured":"Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson (2010) Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput. 39(4): 1637\u20131665 Earlier version in STOC 2008.","journal-title":"SIAM J. Comput."},{"key":"43_CR12","unstructured":"Russell Impagliazzo & Valentine Kabanets (2010). Constructive Proofs of Concentration Bounds. In 14th APPROX-RANDOM, 617\u2013631."},{"key":"43_CR13","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Ran Raz & Avi Wigderson (1994). A Direct Product Theorem. In 9th IEEE Structure in Complexity Theory Conference, 88\u201396.","DOI":"10.1109\/SCT.1994.315814"},{"key":"43_CR14","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In 29th ACM STOC, 220\u2013229."},{"key":"43_CR15","unstructured":"Rahul Jain (2011). New strong direct product results in communication complexity. Electronic Colloquium on Computational Complexity (ECCC) TR11-024."},{"key":"43_CR16","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1016\/j.ipl.2010.07.020","volume":"110","author":"Jain Rahul","year":"2010","unstructured":"Rahul Jain, Hartmut Klauck, Miklos Santha (2010) Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity. Inf. Process. Lett. 110: 893\u2013897","journal-title":"Inf. Process. Lett."},{"key":"43_CR17","unstructured":"Rahul Jain, Attila Pereszl\u00e9nyi & Penghui Yao (2012). A direct product theorem for bounded-round public-coin randomized communication complexity. CoRR abs\/1201.1666."},{"key":"43_CR18","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2010). A Strong Direct Product Theorem for Disjointness. In 42nd ACM STOC, 77\u201386.","DOI":"10.1145\/1806689.1806702"},{"issue":"5","key":"43_CR19","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1137\/05063235X","volume":"36","author":"Klauck Hartmut","year":"2007","unstructured":"Hartmut Klauck, Robert \u0160palek, de Ronald Wolf (2007) Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. SIAM J. Comput. 36(5): 1472\u20131493 Earlier version in FOCS 2004.","journal-title":"SIAM J. Comput."},{"key":"43_CR20","unstructured":"Troy Lee & J\u00e9r\u00e9mie Roland (2011). A Strong Direct Product Theorem for Quantum Query Complexity. CoRR abs\/1104.4468. To appear in CCC 2012."},{"key":"43_CR21","doi-asserted-by":"crossref","unstructured":"Troy Lee, Adi Shraibman & Robert \u0160palek (2008). A Direct Product Theorem for Discrepancy. In 23rd IEEE Conference on Computational Complexity, 71\u201380.","DOI":"10.1109\/CCC.2008.25"},{"key":"43_CR22","doi-asserted-by":"crossref","unstructured":"Ueli M. Maurer (2002). Indistinguishability of Random Systems. In 21st EUROCRYPT, 110\u2013132.","DOI":"10.1007\/3-540-46035-7_8"},{"key":"43_CR23","doi-asserted-by":"crossref","unstructured":"Ueli M. Maurer, Krzysztof Pietrzak & Renato Renner (2007). Indistinguishability Amplification. In 27th CRYPTO, 130\u2013149.","DOI":"10.1007\/978-3-540-74143-5_8"},{"issue":"6","key":"43_CR24","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"Nisan Noam","year":"1991","unstructured":"Noam Nisan (1991) CREW PRAMs and Decision Trees. SIAM J. Comput. 20(6): 999\u20131007 Earlier version in STOC 1989.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"43_CR25","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1137\/S0097539795282444","volume":"28","author":"Nisan Noam","year":"1999","unstructured":"Noam Nisan, Steven Rudich, Michael E. Saks (1999) Products and Help Bits in Decision Trees. SIAM J. Comput. 28(3): 1035\u20131050 Earlier version in FOCS 1994.","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"43_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-003-0175-x","volume":"12","author":"Shaltiel Ronen","year":"2003","unstructured":"Ronen Shaltiel (2003) Towards Proving Strong Direct Product Theorems. Computational Complexity 12(1-2): 1\u201322 Earlier version in CCC 2001.","journal-title":"Computational Complexity"},{"key":"43_CR27","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov (2011). Strong direct product theorems for quantum communication and query complexity. In 43rd ACM STOC, 41\u201350.","DOI":"10.1145\/1993636.1993643"},{"key":"43_CR28","unstructured":"Robert \u0160palek (2008). The Multiplicative Quantum Adversary. In 23rd IEEE Conference on Computational Complexity, 237\u2013248."},{"key":"43_CR29","doi-asserted-by":"crossref","unstructured":"Falk Unger (2009). A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. In 50th IEEE FOCS, 221\u2013229.","DOI":"10.1109\/FOCS.2009.62"},{"issue":"1","key":"43_CR30","doi-asserted-by":"crossref","first-page":"137","DOI":"10.4086\/toc.2008.v004a007","volume":"4","author":"Viola Emanuele","year":"2008","unstructured":"Emanuele Viola, Avi Wigderson (2008) Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1): 137\u2013168 Earlier version in CCC 2007.","journal-title":"Theory of Computing"},{"key":"43_CR31","unstructured":"Andrew Chi-Chih Yao (1977). Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th IEEE FOCS, 222\u2013227."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0043-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0043-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0043-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,29]],"date-time":"2019-06-29T05:06:55Z","timestamp":1561784815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0043-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["43"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0043-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}