{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:50:34Z","timestamp":1764557434774,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2017,9,4]],"date-time":"2017-09-04T00:00:00Z","timestamp":1504483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NRF RF","award":["NRF-NRFF2013-13"],"award-info":[{"award-number":["NRF-NRFF2013-13"]}]},{"name":"Latvian State Research Programme NeXIT","award":["1"],"award-info":[{"award-number":["1"]}]},{"name":"French ANR Blanc program","award":["ANR-12-BS02-005"],"award-info":[{"award-number":["ANR-12-BS02-005"]}]},{"name":"Singapore Ministry of Education and the National Research Foundation"},{"name":"ERC Advanced Grant MQC"},{"name":"European Commission IST STREP project Quantum Algorithms","award":["600700"],"award-info":[{"award-number":["600700"]}]},{"name":"Tier 3 Grant \u201cRandom numbers from quantum processes,\u201d","award":["MOE2012-T3-1-009"],"award-info":[{"award-number":["MOE2012-T3-1-009"]}]},{"name":"RDAM project"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>\n            In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function\n            <jats:italic>f<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            = 2\n            <jats:italic>\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            bits defined by a complete binary tree of NAND gates of depth\n            <jats:italic>k<\/jats:italic>\n            , which achieves\n            <jats:italic>R<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            )\n            <jats:sup>0.7537\u2026<\/jats:sup>\n            ). We show that this is false by giving an example of a total Boolean function\n            <jats:italic>f<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            bits whose deterministic query complexity is \u03a9(\n            <jats:italic>n<\/jats:italic>\n            ) while its zero-error randomized query complexity is \u00d5(\u221a\n            <jats:italic>n<\/jats:italic>\n            ). We further show that the quantum query complexity of the same function is \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/4<\/jats:sup>\n            ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.\n          <\/jats:p>\n          <jats:p>\n            We also construct a total Boolean function\n            <jats:italic>g<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            variables that has zero-error randomized query complexity \u03a9(\n            <jats:italic>n<\/jats:italic>\n            \/ log (\n            <jats:italic>n<\/jats:italic>\n            )) and bounded-error randomized query complexity\n            <jats:italic>R<\/jats:italic>\n            (\n            <jats:italic>g<\/jats:italic>\n            ) = \u00d5(\u221a\n            <jats:italic>n<\/jats:italic>\n            ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is\n            <jats:italic>Q<\/jats:italic>\n            <jats:sub>E<\/jats:sub>\n            (\n            <jats:italic>g<\/jats:italic>\n            ) = \u00d5(\u221a\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            These functions show that the relations\n            <jats:italic>D<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>R<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            ) and\n            <jats:italic>R<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) = \u00d5(\n            <jats:italic>R<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between\n            <jats:italic>Q<\/jats:italic>\n            and\n            <jats:italic>R<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            , a 3\/2-power separation between\n            <jats:italic>Q<\/jats:italic>\n            <jats:sub>E<\/jats:sub>\n            and\n            <jats:italic>R<\/jats:italic>\n            , and a 4th-power separation between approximate degree and bounded-error randomized query complexity.\n          <\/jats:p>\n          <jats:p>All of these examples are variants of a function recently introduced by G\u00f6\u00f6s, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.<\/jats:p>","DOI":"10.1145\/3106234","type":"journal-article","created":{"date-parts":[[2017,9,5]],"date-time":"2017-09-05T12:23:34Z","timestamp":1504614214000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Separations in Query Complexity Based on Pointer Functions"],"prefix":"10.1145","volume":"64","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[{"name":"Faculty of Computing, University of Latvia, Raina Blvd., Latvia"}]},{"given":"Kaspars","family":"Balodis","sequence":"additional","affiliation":[{"name":"Faculty of Computing, University of Latvia, Raina Blvd., Latvia"}]},{"given":"Aleksandrs","family":"Belovs","sequence":"additional","affiliation":[{"name":"Faculty of Computing, University of Latvia, Raina Blvd., Latvia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6912-2338","authenticated-orcid":false,"given":"Troy","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Physical and Mathematical Sciences, Nanyang Technological University and Centre for Quantum Technologies and MajuLab, Singapore"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[{"name":"CNRS, IRIF, University of Paris Dideot, Paris, and Centre for Quantum Technologies and MajuLab, National University of Singapore"}]},{"given":"Juris","family":"Smotrovs","sequence":"additional","affiliation":[{"name":"Faculty of Computing, University of Latvia, Raina Blvd., Latvia"}]}],"member":"320","published-online":{"date-parts":[[2017,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746547"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897644"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488721"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.30"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055105"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1998.0164"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"volume-title":"Proceedings of 2nd Structure in Complexity Theory. 160--173","author":"Hartmanis Juris","key":"e_1_2_1_13_1","unstructured":"Juris Hartmanis and Lane A. Hemachandra . 1987. One-way functions, robustness, and non-isomorphism of NP-complete sets . In Proceedings of 2nd Structure in Complexity Theory. 160--173 . Juris Hartmanis and Lane A. Hemachandra. 1987. One-way functions, robustness, and non-isomorphism of NP-complete sets. In Proceedings of 2nd Structure in Complexity Theory. 160--173."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2016.008"},{"key":"e_1_2_1_15_1","unstructured":"Gatis Midrij\u0101nis. 2004. Exact quantum query complexity for total Boolean functions. arXiv:0403168.  Gatis Midrij\u0101nis. 2004. Exact quantum query complexity for total Boolean functions. arXiv:0403168."},{"key":"e_1_2_1_16_1","unstructured":"Gatis Midrij\u0101nis. 2005. On Randomized and Quantum Query Complexities. arXiv: 0501142.  Gatis Midrij\u0101nis. 2005. On Randomized and Quantum Query Complexities. arXiv: 0501142."},{"key":"e_1_2_1_17_1","volume-title":"35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201915)","volume":"45","author":"Mukhopadhyay Sagnik","year":"2015","unstructured":"Sagnik Mukhopadhyay and Swagato Sanyal . 2015 . Towards better separation between deterministic and randomized query complexity . In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201915) (Leibniz International Proceedings in Informatics (LIPIcs)), Prahladh Harsha and G. Ramalingam (Eds.) , Vol. 45 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 206--220. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2015.206 10.4230\/LIPIcs.FSTTCS.2015.206 Sagnik Mukhopadhyay and Swagato Sanyal. 2015. Towards better separation between deterministic and randomized query complexity. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201915) (Leibniz International Proceedings in Informatics (LIPIcs)), Prahladh Harsha and G. Ramalingam (Eds.), Vol. 45. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 206--220. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2015.206"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220062"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_2_1_20_1","volume-title":"36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916)","volume":"65","author":"Radhakrishnan Jaikumar","year":"2016","unstructured":"Jaikumar Radhakrishnan and Swagato Sanyal . 2016 . The zero-error randomized query complexity of the pointer function . In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen (Eds.) , Vol. 65 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 16:1--16:13. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2016.16 10.4230\/LIPIcs.FSTTCS.2016.16 Jaikumar Radhakrishnan and Swagato Sanyal. 2016. The zero-error randomized query complexity of the pointer function. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201916) (Leibniz International Proceedings in Informatics (LIPIcs)), Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen (Eds.), Vol. 65. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 16:1--16:13. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2016.16"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.44"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060108"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90210-5"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3106234","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3106234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:36Z","timestamp":1750217436000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3106234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,4]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3106234"],"URL":"https:\/\/doi.org\/10.1145\/3106234","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2017,9,4]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}