A Majority Lemma for Randomised Query Complexity.

Mika Göös Gilbert Maystre

Published in: Computational Complexity Conference (2021)

Keyphrases

query complexity
data complexity
membership queries
exact learning
dnf formulas
concept class
expressive power
learning algorithm
active learning
domain knowledge
np complete
conjunctive queries
vc dimension