A Majority Lemma for Randomised Query Complexity.

Mika Göös Gilbert Maystre

Published in: Electron. Colloquium Comput. Complex. (2021)

Keyphrases

query complexity
data complexity
membership queries
exact learning
concept class
resource consumption
dnf formulas
expressive power
integrity constraints
boolean functions