The Zero-Error Randomized Query Complexity of the Pointer Function

Authors Jaikumar Radhakrishnan, Swagato Sanyal



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.16.pdf
  • Filesize: 0.59 MB
  • 13 pages

Document Identifiers

Author Details

Jaikumar Radhakrishnan
Swagato Sanyal

Cite AsGet BibTex

Jaikumar Radhakrishnan and Swagato Sanyal. 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 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FSTTCS.2016.16

Abstract

The pointer function of Goos, Pitassi and Watson and its variants have recently been used to prove separation results among various measures of complexity such as deterministic, randomized and quantum query complexity, exact and approximate polynomial degree, etc. In particular, Ambainis et al. (STOC 2016) obtained the widest possible (quadratic) separations between deterministic and zero-error randomized query complexity, as well as between bounded-error and zero-error randomized query complexity by considering variants of this pointer function. However, as Ambainis et al. pointed out in their work, the precise zero-error complexity of the original pointer function was not known. We show a lower bound of ~Omega(n^{3/4}) on the zero-error randomized query complexity of the pointer function on Theta(n * log(n)) bits; since an ~O(n^{3/4}) upper bound was already shown by Mukhopadhyay and Sanyal (FSTTCS 2015), our lower bound is optimal up to polylog factors. We, in fact, consider a generalization of the original function and obtain lower bounds for it that are optimal up to polylog factors.
Keywords
  • Deterministic Decision Tree
  • Randomized Decision Tree
  • Query Complexity
  • Models of Computation.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Scott Aaronson. A query complexity breakthrough. Shtetl-Optimized. URL: http://www.scottaaronson.com/blog/?p=2325.
  2. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 800-813, 2016. Google Scholar
  3. Manuel Blum and Russell Impagliazzo. Generic oracles and oracle classes (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 118-126, 1987. Google Scholar
  4. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. Google Scholar
  5. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1077-1088, 2015. Google Scholar
  6. Juris Hartmanis and Lane A. Hemachandra. One-way functions, robustness, and the non-isomorphism of np-complete sets. In Proceedings of the Second Annual Conference on Structure in Complexity Theory, Cornell University, Ithaca, New York, USA, June 16-19, 1987, 1987. Google Scholar
  7. Sagnik Mukhopadhyay and Swagato Sanyal. Towards better separation between deterministic and randomized query complexity. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, pages 206-220, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.206.
  8. Noam Nisan. CREW prams and decision trees. SIAM J. Comput., 20(6):999-1007, 1991. Google Scholar
  9. Michael E. Saks and Avi Wigderson. Probabilistic boolean decision trees and the complexity of evaluating game trees. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 29-38, 1986. Google Scholar
  10. Marc Snir. Lower bounds on probabilistic linear decision trees. Theor. Comput. Sci., 38:69-82, 1985. Google Scholar
  11. Gábor Tardos. Query complexity, or why is it difficult to seperate NP^A ∩ coNP^A from P^A by random oracles A? Combinatorica, 9(4):385-392, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail