The Zero-Error Randomized Query Complexity of the Pointer Function

DOI10.4230/LIPICS.FSTTCS.2016.16zbMATH Open1393.68081arXiv1607.01684OpenAlexW2964346110MaRDI QIDQ4636563

Swagato Sanyal, Jaikumar Radhakrishnan

Publication date: 19 April 2018

Abstract: The 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

w i d e t i l d e O m e g a (n^{3 / 4})

on the zero-error randomized query complexity of the pointer function on

T h e t a (n l o g n)

bits; since an

w i d e t i l d e O (n^{3 / 4})

upper bound is already known cite{DBLP:conf/fsttcs/MukhopadhyayS15}, our lower bound is optimal up to a factor of

p o l y l o g, n

.

Full work available at URL: https://arxiv.org/abs/1607.01684

zbMATH Keywords

query complexity models of computation randomized decision tree deterministic decision tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)