An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree.

Andris Ambainis Aleksandrs Belovs

Published in: CCC (2023)

Keyphrases

query complexity
membership queries
dnf formulas
equivalence queries
exact learning
data complexity
concept class
vc dimension