{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:02Z","timestamp":1750307162123,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T00:00:00Z","timestamp":1312156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2011,8]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>f<\/jats:italic>\n            : {0, 1}\n            <jats:italic>n<\/jats:italic>\n            \u2192 {0, 1}. Let\n            <jats:italic>\u03bc<\/jats:italic>\n            be a product probability measure on {0, 1}\n            <jats:italic>n<\/jats:italic>\n            . For\n            <jats:italic>\u03f5<\/jats:italic>\n            \u2265 0, we define\n            <jats:italic>D\u03f5<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ), the\n            <jats:italic>\u03f5-approximate<\/jats:italic>\n            decision tree complexity of\n            <jats:italic>f<\/jats:italic>\n            , to be the minimum depth of a decision tree\n            <jats:italic>T<\/jats:italic>\n            with\n            <jats:italic>\u03bc<\/jats:italic>\n            (\n            <jats:italic>T<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ) \u2260\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            )) \u2264\n            <jats:italic>\u03f5<\/jats:italic>\n            . For\n            <jats:italic>j<\/jats:italic>\n            = 0 or 1 and for\n            <jats:italic>\u03b4<\/jats:italic>\n            \u2265 0, we define\n            <jats:italic>Cj,\u03b4<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ), the\n            <jats:italic>\u03b4-approximate<\/jats:italic>\n            <jats:italic>j<\/jats:italic>\n            -certificate complexity of\n            <jats:italic>f<\/jats:italic>\n            , to be the minimum certificate complexity of a set\n            <jats:italic>A<\/jats:italic>\n            \u2286\n            <jats:italic>\u03a9<\/jats:italic>\n            with\n            <jats:italic>\u03bc<\/jats:italic>\n            (\n            <jats:italic>A\u0394f<\/jats:italic>\n            <jats:sup>\u22121<\/jats:sup>\n            (\n            <jats:italic>j<\/jats:italic>\n            )) \u2264\n            <jats:italic>\u03f5<\/jats:italic>\n            . Note that if\n            <jats:italic>\u03bc<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ) &gt; 0 for all\n            <jats:italic>x<\/jats:italic>\n            then\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) =\n            <jats:italic>D<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) and\n            <jats:italic>Cj<\/jats:italic>\n            <jats:sub>,0<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) =\n            <jats:italic>Cj<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) are the ordinary decision tree and\n            <jats:italic>j<\/jats:italic>\n            -certificate complexities of\n            <jats:italic>f<\/jats:italic>\n            , respectively. We extend the well-known result,\n            <jats:italic>D<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) \u2264\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            )\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) [Blum and Impagliazzo 1987; Hartmanis and Hemachandra 1991; Tardos 1989], proving that for all\n            <jats:italic>\u03f5<\/jats:italic>\n            &gt; 0 there exists a\n            <jats:italic>\u03b4<\/jats:italic>\n            &gt; 0 and a constant\n            <jats:italic>K<\/jats:italic>\n            =\n            <jats:italic>K<\/jats:italic>\n            (\n            <jats:italic>\u03f5<\/jats:italic>\n            ,\n            <jats:italic>\u03b4<\/jats:italic>\n            ) &gt; 0 such that for all\n            <jats:italic>n<\/jats:italic>\n            ,\n            <jats:italic>\u03bc<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            ,\n            <jats:italic>D\u03f5<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) \u2264\n            <jats:italic>K C<\/jats:italic>\n            <jats:sub>1,<\/jats:sub>\n            <jats:italic>\u03b4<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            )\n            <jats:italic>C<\/jats:italic>\n            <jats:sub>0,<\/jats:sub>\n            <jats:italic>\u03b4<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ). We also give a partial answer to a related question on query complexity raised by Tardos [1989]. We prove generalizations of these results to general product probability spaces.\n          <\/jats:p>","DOI":"10.1145\/2003685.2003688","type":"journal-article","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:30:18Z","timestamp":1314711018000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Query Complexity"],"prefix":"10.1145","volume":"3","author":[{"given":"Clifford","family":"Smyth","sequence":"first","affiliation":[{"name":"University of North Carolina Greensboro"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808742"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/3213860"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.30"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-007-0068-z"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62226"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90323-T"},{"key":"e_1_2_1_7_1","unstructured":"Impagliazzo R. and Rudich S. 2000. Personal communication. Impagliazzo R. and Rudich S. 2000. Personal communication."},{"volume-title":"Proceedings of the 15th Annual IEEE Conference on Computational Complexity. IEEE Computer Society","author":"Kahn J.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge UK. Kushilevitz E. and Nisan N. 1997. Communication Complexity . Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399004113"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509942"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2003685.2003688","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2003685.2003688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:32Z","timestamp":1750240472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2003685.2003688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1145\/2003685.2003688"],"URL":"https:\/\/doi.org\/10.1145\/2003685.2003688","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2011,8]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}