Space Complexity vs. Query Complexity.
Oded LachishIlan NewmanAsaf ShapiraPublished in: APPROX-RANDOM (2006)
Keyphrases
- space complexity
- query complexity
- data complexity
- membership queries
- exact learning
- worst case
- arc consistency
- vc dimension
- query evaluation
- space requirements
- resource consumption
- concept class
- dnf formulas
- worst case time complexity
- incomplete information
- np hard
- positive and negative
- expressive power
- theoretical analysis