Separation Between Deterministic and Randomized Query Complexity.

Sagnik Mukhopadhyay Jaikumar Radhakrishnan Swagato Sanyal

Published in: SIAM J. Comput. (2018)

Keyphrases

query complexity
membership queries
data complexity
exact learning
vc dimension
query language
concept class
dnf formulas
learning algorithm
boolean functions
uniform distribution
concept classes
resource consumption