Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.
Ruiwen ChenRahul SanthanamSrikanth SrinivasanPublished in: Electron. Colloquium Comput. Complex. (2015)
Keyphrases
- average case
- worst case
- online algorithms
- lower bound
- worst case analysis
- competitive ratio
- learning algorithm
- average case complexity
- uniform distribution
- computational complexity
- vc dimension
- small number
- online learning
- theoretical analysis
- satisfiability problem
- upper bound
- learning curves
- machine learning
- greedy algorithm
- active learning
- optimal solution