Formula lower bounds via the quantum method

DOI10.1145/3055399.3055472zbMath1370.68142OpenAlexW2626013949MaRDI QIDQ4978064

Avishay Tal

Publication date: 17 August 2017

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

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

zbMATH Keywords

inner productformula complexityaverage-case complexitygraph complexityformula lower boundsbipartite formula complexitysize amplification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (8)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Approximate Degree in Classical and Quantum Computing ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Algorithmic Polynomials ⋮ Unnamed Item ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Unnamed Item

This page was built for publication: Formula lower bounds via the quantum method