{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:49Z","timestamp":1787337589684,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>\n                    We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2\n                    <jats:sup>n<\/jats:sup>\n                    ) as input.\n                  <\/jats:p>\n                  <jats:p>\n                    Our main results are the following: O(N\n                    <jats:sup>\n                      log\n                      <jats:sub>2<\/jats:sub>\n                      3\n                    <\/jats:sup>\n                    log N) algorithms for many common properties, an O(N\n                    <jats:sup>\n                      log\n                      <jats:sub>2<\/jats:sub>\n                      5\n                    <\/jats:sup>\n                    log N) algorithm for block sensitivity, an O(N) algorithm for testing \"quasi symmetry,\" a notion of a \"tree decomposition\" of a Boolean function, proof that the decomposition is unique, and an O(N\n                    <jats:sup>\n                      log\n                      <jats:sub>2<\/jats:sub>\n                    <\/jats:sup>\n                    3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic.\n                  <\/jats:p>\n                  <jats:p>The algorithms discussed have been implemented in a linkable library.<\/jats:p>","DOI":"10.1137\/s0097539700379644","type":"journal-article","created":{"date-parts":[[2003,11,7]],"date-time":"2003-11-07T11:19:22Z","timestamp":1068203962000},"page":"1140-1157","source":"Crossref","is-referenced-by-count":8,"title":["Algorithms for Boolean Function Query Properties"],"prefix":"10.1137","volume":"32","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"S. Aaronson,\n                      Quantum certificate complexity\n                      , in Proceedings of the 18th Annual IEEE Conference on Computational Complexity, Aarhus, Denmark, 2003, IEEE Press, Los Alamitos, CA, 2003, pp. 171\u2013178.","DOI":"10.1109\/CCC.2003.1214418"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"S. Aaronson,\n                      Quantum lower bound for the collision problem\n                      , in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), Montreal, 2002, ACM, New York, 2002, pp. 635\u2013642.","DOI":"10.1145\/509907.509999"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1826"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Andris Ambainis, Ronald de Wolf, Average\u2010case quantum query complexity, Lecture Notes in Comput. Sci., Vol. 1770, Springer, Berlin, 2000, 133\u20131441781727","DOI":"10.1007\/3-540-46541-3_11"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"H. Barnum, M. Saks, and M. Szegedy,\n                      Quantum decision trees and semidefinite programming\n                      , in Proceedings of the 18th Annual IEEE Conference on Computational Complexity, Aarhus, Denmark, 2003, IEEE Press, Los Alamitos, CA, 2003, pp. 179\u2013193.","DOI":"10.1109\/CCC.2003.1214419"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Z. Bar\u2010Yossef, R. Kumar, and D. Sivakumar,\n                      Sampling algorithms: Lower bounds and applications\n                      , in Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC), Crete, 2001, ACM, New York, 2001, pp. 266\u2013275.","DOI":"10.1145\/380752.380810"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"R10","unstructured":"S. L. A. Czort,\n                      The Complexity of Minimizing Disjunctive Normal Form Formulas\n                      , Master\u2019s thesis, University of Aarhus, Aarhus, Denmark, 1999."},{"key":"R11","unstructured":", 39th Annual Symposium on Foundations of Computer Science, Proceedings of the symposium (FOCS \u201998) held in Palo Alto, CA, November 8\u201311, 1998, IEEE Computer Society, 1998, 0\u20130, xiv+7452003b:68005"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00063-0"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Lov Grover, A fast quantum mechanical algorithm for database search, ACM, New York, 1996, 212\u20132191427516","DOI":"10.1145\/237814.237866"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0040"},{"key":"R15","volume-title":"Linear algebra","author":"Hoffman Kenneth","year":"1971"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.4213\/rm892"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0220062"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Saks and A. Wigderson,\n                      Probabilistic Boolean decision trees and the complexity of evaluating game trees\n                      , in Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, Piscataway, NJ, 1986, pp. 29\u201338.","DOI":"10.1109\/SFCS.1986.44"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060108"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"D. Sieling,\n                      Minimization of decision trees is hard to approximate\n                      , in Proceedings of the 18th Annual IEEE Conference on Computational Complexity, Aarhus, Denmark, 2003, IEEE Press, Los Alamitos, CA, 2003, pp. 84\u201392.","DOI":"10.1109\/CCC.2003.1214412"},{"key":"R24","unstructured":"R. Solovay,\n                      Lie groups and quantum circuits\n                      , talk presented at the Workshop on Mathematics of Quantum Computation, Mathematical Sciences Research Institute, Berkeley, CA, 2000."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700379644","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:18Z","timestamp":1787336358000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700379644"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0097539700379644"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700379644","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}