Separations in query complexity using cheat sheets

DOI10.1145/2897518.2897644zbMath1373.68216arXiv1511.01937OpenAlexW3104067947MaRDI QIDQ5361886

Robin Kothari, Shalev Ben-David, Scott Aaronson

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.01937

zbMATH Keywords

separationsquery complexitycheat sheets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (25)

An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Deterministic Communication vs. Partition Number ⋮ Beyond quadratic speedups in quantum attacks on symmetric schemes ⋮ Optimal parallel quantum query algorithms ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ Around the log-rank conjecture ⋮ Query-to-Communication Lifting for BPP ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ Separation Between Deterministic and Randomized Query Complexity ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Algorithmic Polynomials ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ On block sensitivity and fractional block sensitivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quadratically tight relations for randomized query complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extended learning graphs for triangle finding ⋮ Query complexity of generalized Simon's problem ⋮ Unnamed Item

This page was built for publication: Separations in query complexity using cheat sheets