{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:29Z","timestamp":1761621089003,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":15,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,1,8]],"date-time":"2012-01-08T00:00:00Z","timestamp":1325980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000082","name":"Division of Graduate Education","doi-asserted-by":"publisher","award":["DGE-0801525"],"award-info":[{"award-number":["DGE-0801525"]}],"id":[{"id":"10.13039\/100000082","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FG02-05ER41360"],"award-info":[{"award-number":["DE-FG02-05ER41360"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,1,8]]},"DOI":"10.1145\/2090236.2090258","type":"proceedings-article","created":{"date-parts":[[2012,1,10]],"date-time":"2012-01-10T17:02:17Z","timestamp":1326214937000},"page":"249-265","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure"],"prefix":"10.1145","author":[{"given":"Bohua","family":"Zhan","sequence":"first","affiliation":[{"name":"Princeton University"}]},{"given":"Shelby","family":"Kimmel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}]},{"given":"Avinatan","family":"Hassidim","sequence":"additional","affiliation":[{"name":"Bar Ilan University, Google"}]}],"member":"320","published-online":{"date-parts":[[2012,1,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011517.2011524"},{"key":"e_1_3_2_1_2_1","unstructured":"S. Aaronson and A. Ambainis. The need for structure in quantum speedups. arXiv e-prints (0911.0996) Nov. 2009.  S. Aaronson and A. Ambainis. The need for structure in quantum speedups. arXiv e-prints (0911.0996) Nov. 2009."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167097"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a008"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_64"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"B.\n       \n      Johnson\n    .\n      \n  \n   \n  The polynomial degree of recursive fourier sampling. In W. van Dam V. Kendon and S. Severini editors Theory of Quantum Computation Communication and Cryptography volume \n  6519\n   of \n  Lecture Notes in Computer Science pages \n  104\n  --\n  112\n  . \n  Springer Berlin\/Heidelberg 2011\n  .   B. Johnson. The polynomial degree of recursive fourier sampling. In W. van Dam V. Kendon and S. Severini editors Theory of Quantum Computation Communication and Cryptography volume 6519 of Lecture Notes in Computer Science pages 104--112. Springer Berlin\/Heidelberg 2011.","DOI":"10.1007\/978-3-642-18073-6_9"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/5992.909000"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374394"},{"key":"e_1_3_2_1_11_1","unstructured":"B. W. Reichardt. Faster quantum algorithm for evaluating game trees. arXiv e-prints (0907.1623) July 2009.  B. W. Reichardt. Faster quantum algorithm for evaluating game trees. arXiv e-prints (0907.1623) July 2009."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.44"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365701"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"event":{"name":"ITCS '12: Innovations in Theoretical Computer Science","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge Massachusetts","acronym":"ITCS '12"},"container-title":["Proceedings of the 3rd Innovations in Theoretical Computer Science Conference"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090258","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2090236.2090258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:46Z","timestamp":1750241206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,8]]},"references-count":15,"alternative-id":["10.1145\/2090236.2090258","10.1145\/2090236"],"URL":"https:\/\/doi.org\/10.1145\/2090236.2090258","relation":{},"subject":[],"published":{"date-parts":[[2012,1,8]]},"assertion":[{"value":"2012-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}