{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T09:09:29Z","timestamp":1725786569837},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897524","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"800-813","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Separations in query complexity based on pointer functions"],"prefix":"10.1145","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[{"name":"University of Latvia, Latvia"}]},{"given":"Kaspars","family":"Balodis","sequence":"additional","affiliation":[{"name":"University of Latvia, Latvia"}]},{"given":"Aleksandrs","family":"Belovs","sequence":"additional","affiliation":[{"name":"CWI, Netherlands"}]},{"given":"Troy","family":"Lee","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore \/ National University of Singapore, Singapore"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[{"name":"CNRS, France \/ National University of Singapore, Singapore"}]},{"given":"Juris","family":"Smotrovs","sequence":"additional","affiliation":[{"name":"University of Latvia, Latvia"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746547"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488721"},{"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","unstructured":"arXiv:quant-ph\/9802049. arXiv:quant-ph\/9802049."},{"key":"e_1_3_2_1_5_1","volume-title":"A super-Grover separation between randomized and quantum query complexities. arXiv:1506.08106","author":"Ben-David S.","year":"2015","unstructured":"S. Ben-David . A super-Grover separation between randomized and quantum query complexities. arXiv:1506.08106 , 2015 . S. Ben-David. A super-Grover separation between randomized and quantum query complexities. arXiv:1506.08106, 2015."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.30"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_2_1_8_1","series-title":"LNCS","first-page":"831","volume-title":"Proc. of 25th ICALP","author":"Brassard G.","unstructured":"G. Brassard , P. H\u00f8yer , and A. Tapp . Quantum counting . In Proc. of 25th ICALP , volume 1443 of LNCS , pages 820\u2013 831 . Springer, 1998. G. Brassard, P. H\u00f8yer, and A. Tapp. Quantum counting. In Proc. of 25th ICALP, volume 1443 of LNCS, pages 820\u2013831. Springer, 1998."},{"key":"e_1_3_2_1_9_1","unstructured":"arXiv:quant-ph\/9805082. arXiv:quant-ph\/9805082."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1998.0164"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_1_15_1","first-page":"173","volume-title":"Proceedings of 2nd Structure in Complexity Theory","author":"Hartmanis J.","year":"1987","unstructured":"J. Hartmanis and L. A. Hemachandra . One-way functions, robustness, and non-isomorphism of NP-complete sets . In Proceedings of 2nd Structure in Complexity Theory , pages 160\u2013 173 , 1987 . J. Hartmanis and L. A. Hemachandra. One-way functions, robustness, and non-isomorphism of NP-complete sets. In Proceedings of 2nd Structure in Complexity Theory, pages 160\u2013173, 1987."},{"key":"e_1_3_2_1_16_1","volume-title":"On fractional block sensitivity. ECCC:2013\/168","author":"Kulkarni R.","year":"2013","unstructured":"R. Kulkarni and A. Tal . On fractional block sensitivity. ECCC:2013\/168 , 2013 . R. Kulkarni and A. Tal. On fractional block sensitivity. ECCC:2013\/168, 2013."},{"key":"e_1_3_2_1_17_1","volume-title":"Exact quantum query complexity for total boolean functions. arXiv:quant-ph\/0403168","author":"G. Midrij\u00af","year":"2004","unstructured":"G. Midrij\u00af anis. Exact quantum query complexity for total boolean functions. arXiv:quant-ph\/0403168 , 2004 . G. Midrij\u00af anis. Exact quantum query complexity for total boolean functions. arXiv:quant-ph\/0403168, 2004."},{"key":"e_1_3_2_1_18_1","volume-title":"On randomized and quantum query complexities. arXiv:quant-ph\/0501142","author":"G. Midrij\u00af","year":"2005","unstructured":"G. Midrij\u00af anis. On randomized and quantum query complexities. arXiv:quant-ph\/0501142 , 2005 . G. Midrij\u00af anis. On randomized and quantum query complexities. arXiv:quant-ph\/0501142, 2005."},{"key":"e_1_3_2_1_19_1","volume-title":"Towards better separation between deterministic and randomized query complexity. arXiv:1506.06399","author":"Mukhopadhyay S.","year":"2015","unstructured":"S. Mukhopadhyay and S. Sanyal . Towards better separation between deterministic and randomized query complexity. arXiv:1506.06399 , 2015 . S. Mukhopadhyay and S. Sanyal. Towards better separation between deterministic and randomized query complexity. arXiv:1506.06399, 2015."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220062"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.44"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060108"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90210-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge MA USA","acronym":"STOC '16"},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T02:01:13Z","timestamp":1673229673000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":26,"alternative-id":["10.1145\/2897518.2897524","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897524","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}