A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes.

Noga Ron-Zewi Madhu Sudan

Published in: APPROX-RANDOM (2012)

Keyphrases

upper bound
query complexity
concept class
vc dimension
lower bound
concept classes
worst case
membership queries
data complexity
upper and lower bounds
dnf formulas
databases
generalization error
lower and upper bounds
resource consumption
exact learning