Separations in Query Complexity Based on Pointer Functions

DOI10.1145/3106234zbMath1426.68109arXiv1506.04719OpenAlexW2752597570MaRDI QIDQ4640297

Troy Lee, Miklos Santha, J. Smotrovs, Kaspars Balodis, Aleksandrs Belovs, Andris Ambainis

Publication date: 17 May 2018

Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

Monte Carloquantum algorithmsdeterministic algorithmsdecision treesrandomized algorithmsLas Vegasquery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Time-Space Complexity Advantages for Quantum Computing, Deterministic Communication vs. Partition Number, Beyond quadratic speedups in quantum attacks on symmetric schemes, Optimal separation in exact query complexities for Simon's problem, Optimal parallel quantum query algorithms, Around the log-rank conjecture, An exact quantum algorithm for a restricted subtraction game, Lifting query complexity to time-space complexity for two-way finite automata, Parity decision tree in classical-quantum separations for certain classes of Boolean functions, Query-to-Communication Lifting for BPP, A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$, Unnamed Item, Separation Between Deterministic and Randomized Query Complexity, Revisiting Deutsch-Jozsa algorithm, Quantum Query Algorithms are Completely Bounded Forms., Quantum Query Algorithms Are Completely Bounded Forms, A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function, Quantum algorithms on Walsh transform and Hamming distance for Boolean functions, Unnamed Item, Unnamed Item, Extended learning graphs for triangle finding, Query complexity of generalized Simon's problem, Equality alone does not simulate randomness, Evaluation of exact quantum query complexities by semidefinite programming