The Zero-Error Randomized Query Complexity of the Pointer Function

DOI10.4230/LIPICS.FSTTCS.2016.16MaRDI QIDQ4636563zbMATH OpenOpenAlexFDO

Authors Swagato Sanyal, Jaikumar Radhakrishnan

Publication date 19 April 2018

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

zbMATH Keywords

deterministic decision treemodels of computationquery complexityrandomized decision tree

Mathematics Subject Classification ID

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

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 $widetildeOmega(n^{3/4})$ on the zero-error randomized query complexity of the pointer function on $Theta(nlogn)$ bits; since an $widetildeO(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$.

Recommendations

• Randomized query complexity of sabotaged and composed functions
• scientific article; zbMATH DE number 6913819
• A composition theorem for randomized query complexity
• scientific article; zbMATH DE number 7711600
• Query complexity in errorless hardness amplification
• Query complexity in errorless hardness amplification

Cited in

(6)

• The influence lower bound via query elimination
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• Towards better separation between deterministic and randomized query complexity
• Separation between deterministic and randomized query complexity
• Computing and Combinatorics
• Separations between combinatorial measures for transitive functions

This page was built for publication: The Zero-Error Randomized Query Complexity of the Pointer Function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636563)