A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.

Dmitry Gavinsky Troy Lee Miklos Santha Swagato Sanyal

Published in: ICALP (2019)

Keyphrases

query complexity
data complexity
membership queries
exact learning
worst case
dnf formulas
special case
knowledge representation
uniform distribution
vc dimension