{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:36Z","timestamp":1787341356512,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"TCS Fellowship"},{"DOI":"10.13039\/501100001502","name":"Department of Atomic Energy, Government of India","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001502","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Saks and Wigderson [in Proceedings of the $27$th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that $R_0(f) = \\Omega(D(f)^{0.753\\ldots})$ for all Boolean functions $f$, where $R_0$ denotes the randomized zero-error query complexity and $D$ denotes the deterministic query complexity. We show that for the pointer function $\\mathsf{GPW}^{r \\times s}$ defined by G\u00f6\u00f6s, Pitassi, and Watson [in Proceedings of the $56$th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) $R_1(\\mathsf{GPW}^{r \\times s}) = \\widetilde{\\Theta}({r+s})$ and (b) $R_1(\\overline{\\mathsf{GPW}^{r \\times s}}) = \\widetilde{\\Theta}(r+\\sqrt{r}s)$, where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(\\mathsf{GPW}^{s^2 \\times s}) = O(D(\\mathsf{GPW}^{s^2 \\times s})^{2\/3})$, thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(\\mathsf{GPW}^{s \\times s})=\\widetilde{O}(R_0(\\mathsf{GPW}^{s \\times s})^{2\/3})$, thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.<\/jats:p>","DOI":"10.1137\/17m1124115","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T13:14:00Z","timestamp":1534857240000},"page":"1644-1666","source":"Crossref","is-referenced-by-count":3,"title":["Separation Between Deterministic and Randomized Query Complexity"],"prefix":"10.1137","volume":"47","author":[{"given":"Sagnik","family":"Mukhopadhyay","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jaikumar","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Swagato","family":"Sanyal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"atypb1","unstructured":"S. Aaronson,\n                      A query complexity breakthrough\n                      ,https:\/\/www.scottaaronson.com\/blog\/?p=2325(June 17, 2015)."},{"key":"atypb2","first-page":"800","author":"Ambainis A.","year":"2016","journal-title":"New York"},{"key":"atypb3","first-page":"863","author":"Aaronson S.","year":"2016","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"atypb5","first-page":"118","author":"Blum M.","year":"1987","journal-title":"Washington, DC"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00261-7"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi,\n                      Concentration of Measure for the Analysis of Randomized Algorithms\n                      , Cambridge University Press, Cambridge, 2009.","DOI":"10.1017\/CBO9780511581274"},{"key":"atypb8","first-page":"5","author":"G\u00f6\u00f6s M.","year":"2016","journal-title":"Germany"},{"key":"atypb9","first-page":"1077","author":"G\u00f6\u00f6s M.","year":"2015","journal-title":"NJ"},{"key":"atypb10","first-page":"160","author":"Hartmanis J.","year":"1987","journal-title":"Washington, DC"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20598"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"A. W. Marshall, I. Olkin, and B. C. Arnold,\n                      Inequalities: Theory of Majorization and Its Applications\n                      , Springer, New York, 2010.","DOI":"10.1007\/978-0-387-68276-1"},{"key":"atypb13","first-page":"206","author":"Mukhopadhyay S.","year":"2015","journal-title":"Germany"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0220062"},{"key":"atypb15","first-page":"16","author":"Radhakrishnan J.","year":"2016","journal-title":"Germany"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90053-0"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Santha,\n                      On the Monte Carlo boolean decision tree complexity of read-once formulae\n                      , in Proceedings of the 6th Annual Conference on Structure in Complexity Theory, IEEE Computer Society, Los Alamitos, CA, 1991, pp. 180-187.","DOI":"10.1109\/SCT.1991.160259"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90210-5"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M. E. Saks and A. Wigderson,\n                      Probabilistic boolean decision trees and the complexity of evaluating game trees\n                      , in Proceedings of the 27th FOCS, IEEE Computer Society, Los Alamitos, CA, 1996, pp. 29-38.","DOI":"10.1109\/SFCS.1986.44"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125350"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1124115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:53Z","timestamp":1787339693000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1124115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1124115"],"URL":"https:\/\/doi.org\/10.1137\/17m1124115","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}