Sampling lower bounds: boolean average-case and permutations.
Emanuele ViolaPublished in: Electron. Colloquium Comput. Complex. (2018)
Keyphrases
- average case
- lower bound
- worst case
- vc dimension
- average case complexity
- upper bound
- online algorithms
- sample size
- worst case analysis
- uniform distribution
- boolean functions
- competitive ratio
- learning curves
- sample complexity
- branch and bound
- np hard
- real valued
- upper and lower bounds
- optimal solution
- objective function
- lower and upper bounds
- data sets
- linear programming
- membership queries
- concept classes
- machine learning