{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T22:47:26Z","timestamp":1754261246325},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,6,21]],"date-time":"2016-06-21T00:00:00Z","timestamp":1466467200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00037-016-0139-6","type":"journal-article","created":{"date-parts":[[2016,6,22]],"date-time":"2016-06-22T14:53:52Z","timestamp":1466607232000},"page":"723-735","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Quantum Query Complexity of Almost All Functions with Fixed On-set Size"],"prefix":"10.1007","volume":"25","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masaki","family":"Nakanishi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rudy","family":"Raymond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seiichiro","family":"Tani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigeru","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,21]]},"reference":[{"issue":"1","key":"139_CR1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0020-0190(99)00079-4","volume":"71","author":"Andris Ambainis","year":"1999","unstructured":"Ambainis Andris (1999) A Note on Quantum Black-Box Complexity of Almost all Boolean Functions. Information Processing Letters 71(1): 5\u20137","journal-title":"Information Processing Letters"},{"key":"139_CR2","unstructured":"Andris Ambainis, Arturs Ba\u010dkurs, Juris Smotrovs & Ronald de Wolf (2013). Optimal quantum query bounds for almost all Boolean functions. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), 446\u2013453."},{"key":"139_CR3","doi-asserted-by":"crossref","unstructured":"A. Ambainis, A. M. Childs, B. W. Reichardt, R. \u0160palek, & S. Zhang (2010). Any AND-OR Formula of Size $${{N}}$$ N Can Be Evaluated in Time $${{N}^{1\/2+o(1)}}$$ N 1 \/ 2 + o ( 1 ) on a Quantum Computer. SIAM Journal on Computing 39(6): 2513\u20132530","DOI":"10.1137\/080712167"},{"key":"139_CR4","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra & Shigeru Yamashita (2004). Quantum Identification of Boolean Oracles. In Proceedings of the Twenty-First Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201904), volume 2996 of Lecture Notes in Computer Science, 105\u2013116. Springer.","DOI":"10.1007\/978-3-540-24749-4_10"},{"issue":"1","key":"139_CR5","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.tcs.2006.12.013","volume":"378","author":"Andris Ambainis","year":"2007","unstructured":"Ambainis Andris, Iwama Kazuo, Kawachi Akinori, Raymond Rudy, Yamashita Shigeru (2007) Improved algorithms for quantum identification of Boolean oracles. Theoretical Computer Science 378(1): 41\u201353","journal-title":"Theoretical Computer Science"},{"key":"139_CR6","unstructured":"Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani & Shigeru Yamashita (2009). Average\/Worst-Case Gap of Quantum Query Complexities by On-Set Size. arXiv:0908.2468 ."},{"issue":"2","key":"139_CR7","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0166-218X(94)00008-2","volume":"61","author":"Martin Anthony","year":"1995","unstructured":"Anthony Martin (1995) Classification by Polynomial Surfaces. Discrete Applied Mathematics 61(2): 91\u2013103","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"139_CR8","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"Robert Beals","year":"2001","unstructured":"Beals Robert, Buhrman Harry, Cleve Richard, Mosca Michele, de Wolf Ronald (2001) Quantum lower bounds by polynomials. Journal of the ACM 48(4): 778\u2013797","journal-title":"Journal of the ACM"},{"issue":"6","key":"139_CR9","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1137\/0115129","volume":"15","author":"A. J. Bernstein","year":"1967","unstructured":"Bernstein A. J. (1967) Maximally Connected Arrays on the $${N}$$ N -Cube. SIAM Journal on Applied Mathematics 15(6): 1485\u20131489","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"139_CR10","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Nikolay Vereshchagin & Ronald de Wolf (2007). On Computation and Communication with Small Bias. In Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, 24\u201332.","DOI":"10.1109\/CCC.2007.18"},{"issue":"1","key":"139_CR11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"Harry Buhrman","year":"2002","unstructured":"Buhrman Harry, de Wolf Ronald (2002) Complexity measures and decision tree complexity: a survey. Theoretical Computer Science 288(1): 21\u201343","journal-title":"Theoretical Computer Science"},{"key":"139_CR12","doi-asserted-by":"crossref","unstructured":"Wim van Dam (1998). Quantum Oracle Interrogation: Getting All Information for Almost Half the Price. In Proceedings of the Thirty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201998), 362\u2013367.","DOI":"10.1109\/SFCS.1998.743486"},{"key":"139_CR13","doi-asserted-by":"crossref","unstructured":"Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC\u201996), 212\u2013219.","DOI":"10.1145\/237814.237866"},{"issue":"1","key":"139_CR14","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"L. H. Harper","year":"1964","unstructured":"Harper L. H. (1964) Optimal Assignments of Numbers to Vertices. SIAM Journal on Applied Mathematics 12(1): 131\u2013135","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"139_CR15","doi-asserted-by":"crossref","unstructured":"Aram W. Harrow, & Andreas Winter (2012) How Many Copies are Needed for State Discrimination?. IEEE Transactions on Information Theory 58(1): 1\u20132","DOI":"10.1109\/TIT.2011.2169544"},{"key":"139_CR16","unstructured":"Robin Kothari (2014). An optimal quantum algorithm for the oracle identification problem. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 482\u2013493. Also available at arXiv:1311.7685 ."},{"key":"139_CR17","doi-asserted-by":"crossref","unstructured":"Ashley Montanaro, Harumichi Nishimura & Rudy Raymond (2008). Unbounded-Error Quantum Query Complexity. In Proceedings of the Nineteeth International Symposium on Algorithms and Computation (ISAAC\u201908), volume 5369 of Lecture Notes in Computer Science, 919\u2013930. Springer.","DOI":"10.1007\/978-3-540-92182-0_80"},{"issue":"6","key":"139_CR18","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"Noam Nisan","year":"1991","unstructured":"Nisan Noam (1991) CREW PRAMs and Decision Trees. SIAM Journal on Computing 20(6): 999\u20131007","journal-title":"SIAM Journal on Computing"},{"key":"139_CR19","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF01683269","volume":"10","author":"Nicholas Pippenger","year":"1977","unstructured":"Pippenger Nicholas (1977) Information Theory and the Complexity of Boolean Functions. Mathematical Systems Theory 10: 129\u2013167","journal-title":"Mathematical Systems Theory"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0139-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0139-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0139-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T12:50:16Z","timestamp":1498308616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0139-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,21]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["139"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0139-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,21]]}}}