An Average-Case Lower Bound against ACC^0.
Igor Carboni OliveiraRuiwen ChenRahul SanthanamPublished in: Electron. Colloquium Comput. Complex. (2017)
Keyphrases
- average case
- lower bound
- worst case
- competitive ratio
- upper bound
- vc dimension
- worst case analysis
- online algorithms
- np hard
- branch and bound
- average case complexity
- uniform distribution
- sample complexity
- sample complexity bounds
- approximation algorithms
- learning curves
- lower and upper bounds
- objective function
- upper and lower bounds
- optimal solution
- pac learning