Query Complexity in Errorless Hardness Amplification.
Thomas WatsonPublished in: Comput. Complex. (2015)
Keyphrases
- query complexity
- data complexity
- learning theory
- concept class
- membership queries
- np complete
- phase transition
- worst case
- np hard
- exact learning
- computational complexity
- resource consumption
- vc dimension
- query evaluation
- dnf formulas
- databases
- concept classes
- equivalence queries
- expressive power
- lower bound
- learning algorithm
- machine learning