{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T04:30:38Z","timestamp":1770438638024,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T00:00:00Z","timestamp":1367280000000},"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":[[2013,6]]},"DOI":"10.1007\/s00037-013-0066-8","type":"journal-article","created":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T03:57:14Z","timestamp":1367380634000},"page":"429-462","source":"Crossref","is-referenced-by-count":7,"title":["A strong direct product theorem for quantum query complexity"],"prefix":"10.1007","volume":"22","author":[{"given":"Troy","family":"Lee","sequence":"first","affiliation":[]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,30]]},"reference":[{"issue":"4","key":"66_CR1","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"Ambainis Andris","year":"2002","unstructured":"Andris Ambainis (2002) Quantum Lower Bounds by Quantum Arguments. Journal of Computer and System Sciences 64(4): 750\u2013767","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"66_CR2","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.jcss.2005.06.006","volume":"72","author":"Ambainis Andris","year":"2006","unstructured":"Andris Ambainis (2006) Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences 72(2): 220\u2013238","journal-title":"Journal of Computer and System Sciences"},{"key":"66_CR3","doi-asserted-by":"crossref","first-page":"181","DOI":"10.26421\/QIC10.3-4-1","volume":"10","author":"Ambainis Andris","year":"2010","unstructured":"Andris Ambainis, Andrew M. Childs, Fran\u00e7ois Le Gall, Seiichiro Tani (2010a) The quantum query complexity of certification. Quantum Information and Computation 10: 181\u2013188","journal-title":"Quantum Information and Computation"},{"issue":"6","key":"66_CR4","doi-asserted-by":"crossref","first-page":"2513","DOI":"10.1137\/080712167","volume":"39","author":"Ambainis Andris","year":"2010","unstructured":"Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert \u0160palek, Shengyu Zhang (2010b) Any AND-OR Formula of Size N Can Be Evaluated in Time N 1\/2+o(1) on a Quantum Computer. SIAM Journal on Computing 39(6): 2513","journal-title":"SIAM Journal on Computing"},{"key":"66_CR5","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 Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 167\u2013177. IEEE Computer Society.","DOI":"10.1109\/CCC.2011.24"},{"key":"66_CR6","unstructured":"Andris Ambainis, Robert \u0160palek & Ronald de Wolf (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, 618\u2013633. ACM. ISBN 1-59593-134-1."},{"key":"66_CR7","doi-asserted-by":"crossref","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca & Ronald de Wolf (1998). Quantum Lower Bounds by Polynomials. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 352. IEEE Computer Society. ISBN 0-8186-9172-7.","DOI":"10.1109\/SFCS.1998.743485"},{"key":"66_CR8","unstructured":"Aleksandrs Belovs (2011). Personal communication."},{"key":"66_CR9","unstructured":"Rajendra Bhatia (2007). Positive definite matrices. Princeton University Press."},{"issue":"1","key":"66_CR10","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. Theoretical Computer Science 288(1): 21\u201343","journal-title":"Theoretical Computer Science"},{"key":"66_CR11","doi-asserted-by":"crossref","first-page":"119","DOI":"10.4086\/toc.2009.v005a005","volume":"5","author":"M. Childs Andrew","year":"2009","unstructured":"Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David Yeung (2009) Discrete-query quantum algorithm for NAND trees. Theory of Computing 5: 119\u2013123","journal-title":"Theory of Computing"},{"key":"66_CR12","unstructured":"Thomas M. Cover & Joy A. Thomas (2006). Elements of Information Theory. Wiley."},{"key":"66_CR13","doi-asserted-by":"crossref","unstructured":"Andrew Drucker (2011). Improved Direct Product Theorems for Randomized Query Complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 1\u201311. IEEE Computer Society.","DOI":"10.1109\/CCC.2011.29"},{"key":"66_CR14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.4086\/toc.2008.v004a008","volume":"4","author":"Farhi Edward","year":"2008","unstructured":"Edward Farhi, Jeffrey Goldstone, Sam Gutmann (2008) A Quantum Algorithm for the Hamiltonian NAND Tree. Theory of Computing 4: 169\u2013190","journal-title":"Theory of Computing"},{"key":"66_CR15","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Noam Nisan & Avi Wigderson (2011). On Yao\u2019s XOR-Lemma. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, volume 6650 of Lecture Notes in Computer Science, 273\u2013301. Springer.","DOI":"10.1007\/978-3-642-22670-0_23"},{"key":"66_CR16","doi-asserted-by":"crossref","unstructured":"Peter H\u00f8yer, Troy Lee & Robert \u0160palek (2007). Negative weights make adversaries stronger. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 526\u2013535. ACM. ISBN 978-1-59593-631-8.","DOI":"10.1145\/1250790.1250867"},{"key":"66_CR17","unstructured":"Rahul Jain, Attila Pereszlenyi & Penghui Yao (2012). A direct product theorem for bounded-round public coin randomized communication complexity. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society."},{"issue":"5","key":"66_CR18","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 Journal on Computing 36(5): 1472\u20131493","journal-title":"SIAM Journal on Computing"},{"key":"66_CR19","doi-asserted-by":"crossref","unstructured":"Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert \u0160palek & Mario Szegedy (2011). Quantum query complexity of state conversion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 344\u2013353. IEEE Computer Society.","DOI":"10.1109\/FOCS.2011.75"},{"key":"66_CR20","unstructured":"Troy Lee & J\u00e9r\u00e9mie Roland (2012). A strong direct product theorem for quantum query complexity. In Proceedings of the 27th IEEE Conference on Computational Complexity, 234\u2013246. IEEE Computer Society."},{"key":"66_CR21","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, 71\u201380. IEEE Computer Society.","DOI":"10.1109\/CCC.2008.25"},{"key":"66_CR22","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s00493-007-2160-5","volume":"27","author":"Linial Nati","year":"2007","unstructured":"Nati Linial, Shahar Mendelson, Gideon Schechtman, Adi Shraibman (2007) Complexity measures of sign matrices. Combinatorica 27: 439\u2013463","journal-title":"Combinatorica"},{"issue":"3","key":"66_CR23","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1002\/rsa.20232","volume":"34","author":"Linial Nati","year":"2009","unstructured":"Nati Linial, Adi Shraibman (2009) Lower bounds in communication complexity based on factorization norms. Random Structures and Algorithms 34(3): 368\u2013394","journal-title":"Random Structures and Algorithms"},{"key":"66_CR24","unstructured":"Michael A. Nielsen & Isaac L. Chuang (2000). Quantum Computation and Quantum Information. Cambridge University Press."},{"issue":"3","key":"66_CR25","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"Raz Ran","year":"1998","unstructured":"Ran Raz (1998) A Parallel Repetition Theorem. SIAM Journal on Computing 27(3): 763\u2013803","journal-title":"SIAM Journal on Computing"},{"key":"66_CR26","doi-asserted-by":"crossref","unstructured":"Ben W. Reichardt (2009). Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 544\u2013551. IEEE Computer Society. ISSN 0272-5428.","DOI":"10.1109\/FOCS.2009.55"},{"key":"66_CR27","doi-asserted-by":"crossref","unstructured":"Ben W. Reichardt (2011). Reflections for quantum query algorithms. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 560\u2013569. SIAM.","DOI":"10.1137\/1.9781611973082.44"},{"key":"66_CR28","unstructured":"Ben W. Reichardt & Robert \u0160palek (2008). Span-program-based quantum algorithm for evaluating formulas. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 103\u2013112. ACM. ISBN 978-1-60558-047-0."},{"issue":"1-2","key":"66_CR29","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","journal-title":"Computational Complexity"},{"key":"66_CR30","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov (2011). Strong direct product theorems for quantum communication and query complexity. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 41\u201350. ACM.","DOI":"10.1145\/1993636.1993643"},{"key":"66_CR31","unstructured":"Robert \u0160palek (2008). The Multiplicative Quantum Adversary. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 237\u2013248. IEEE Computer Society. ISBN 978-0-7695-3169-4."},{"key":"66_CR32","doi-asserted-by":"crossref","unstructured":"Falk Unger (2009). A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 221\u2013229. IEEE Computer Society.","DOI":"10.1109\/FOCS.2009.62"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0066-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-013-0066-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0066-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T17:17:29Z","timestamp":1644945449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-013-0066-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,30]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["66"],"URL":"https:\/\/doi.org\/10.1007\/s00037-013-0066-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,30]]}}}