The polynomial method strikes back: tight quantum query bounds via dual polynomials
From MaRDI portal
Publication:5230298
DOI10.1145/3188745.3188784zbMath1427.68085arXiv1710.09079OpenAlexW3099921078MaRDI QIDQ5230298
Justin Thaler, Robin Kothari, Mark Bun
Publication date: 22 August 2019
Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.09079
Related Items (15)
Approximate Degree in Classical and Quantum Computing ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithmic Polynomials ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ Quantum algorithm for the multicollision problem ⋮ A quantum evolving secret sharing scheme ⋮ Unnamed Item ⋮ Query complexity of generalized Simon's problem ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Unnamed Item
This page was built for publication: The polynomial method strikes back: tight quantum query bounds via dual polynomials
