Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem

DOI10.1145/3406325.3451047arXiv2010.12629OpenAlexW3169681537MaRDI QIDQ6065256

Shalev Ben-David, Shravas Rao, Scott Aaronson, Avishay Tal, Robin Kothari

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://arxiv.org/abs/2010.12629

zbMATH Keywords

query complexityquantum query complexityapproximate degree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Approximate Degree in Classical and Quantum Computing ⋮ Around the log-rank conjecture ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

This page was built for publication: Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem