Algorithmic polynomials

DOI10.1145/3188745.3188958zbMath1428.68159arXiv1801.04607OpenAlexW2808904471MaRDI QIDQ5230299

Alexander A. Sherstov

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/1801.04607

zbMATH Keywords

quantum query complexitysurjectivity problemapproximate degree\(k\)-CNF formulas\(k\)-DNF formulas\(k\)-element distinctness problem\(k\)-subset sum problem

Mathematics Subject Classification ID

Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (6)

Approximate Degree in Classical and Quantum Computing ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity

This page was built for publication: Algorithmic polynomials