The black-box query complexity of polynomial summation.
Ali JumaValentine KabanetsCharles RackoffAmir ShpilkaPublished in: Electron. Colloquium Comput. Complex. (2007)
Keyphrases
- black box
- query complexity
- equivalence queries
- membership queries
- dnf formulas
- data complexity
- black boxes
- exact learning
- white box
- white box testing
- database
- concept class
- resource consumption
- test cases
- learning algorithm
- data model
- target concept
- upper and lower bounds
- vc dimension
- boolean functions
- query evaluation
- error rate
- integration testing
- feature space