License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.16
URN: urn:nbn:de:0030-drops-68514
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6851/
Go to the corresponding LIPIcs Volume Portal

Radhakrishnan, Jaikumar ; Sanyal, Swagato

The Zero-Error Randomized Query Complexity of the Pointer Function

pdf-format:
LIPIcs-FSTTCS-2016-16.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{radhakrishnan_et_al:LIPIcs:2016:6851,
  author =	{Jaikumar Radhakrishnan and Swagato Sanyal},
  title =	{{The Zero-Error Randomized Query Complexity of the Pointer Function}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6851},
  URN =		{urn:nbn:de:0030-drops-68514},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.16},
  annote =	{Keywords: Deterministic Decision Tree, Randomized Decision Tree, Query Complexity, Models of Computation.}
}

Keywords: Deterministic Decision Tree, Randomized Decision Tree, Query Complexity, Models of Computation.
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI