An optimal separation of randomized and Quantum query complexity

DOI10.1145/3406325.3451019OpenAlexW3089688728MaRDI QIDQ6065253

Alexander A. Sherstov, Unnamed Author, Unnamed Author

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3406325.3451019

zbMATH Keywords

communication complexityquery complexityFourier analysis of Boolean functionsforrelationFourier weight of decision treesquantum-classical separations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Beyond quadratic speedups in quantum attacks on symmetric schemes ⋮ Lifting query complexity to time-space complexity for two-way finite automata

This page was built for publication: An optimal separation of randomized and Quantum query complexity