ECCC-Report TR16-103https://eccc.weizmann.ac.il/report/2016/103Comments and Revisions published for TR16-103en-usWed, 06 Jul 2016 18:55:17 +0300
Paper TR16-103
| The zero-error randomized query complexity of the pointer function. |
Swagato Sanyal,
Jaikumar Radhakrishnan
https://eccc.weizmann.ac.il/report/2016/103The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson
\cite{DBLP:journals/eccc/GoosP015a} and its variants have recently
been used to prove separation results among various measures of
complexity such as deterministic, randomized and quantum query
complexities, exact and approximate polynomial degrees, etc. In
particular, 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, have been obtained by considering {\em
variants}~\cite{DBLP:journals/corr/AmbainisBBL15} of this
pointer function.
However, as was pointed out in
\cite{DBLP:journals/corr/AmbainisBBL15}, the precise zero-error
complexity of the original pointer function was not known. We show a
lower bound of $\widetilde{\Omega}(n^{3/4})$ on the zero-error
randomized query complexity of the pointer function on $\Theta(n \log
n)$ bits; since an $\widetilde{O}(n^{3/4})$ upper bound is already
known \cite{DBLP:conf/fsttcs/MukhopadhyayS15}, our lower bound is
optimal up to a factor of $\polylog\, n$.Wed, 06 Jul 2016 18:55:17 +0300https://eccc.weizmann.ac.il/report/2016/103