Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.
Ruiwen ChenRahul SanthanamSrikanth SrinivasanPublished in: Computational Complexity Conference (2016)
Keyphrases
- average case
- worst case
- lower bound
- worst case analysis
- online algorithms
- upper bound
- average case complexity
- computational complexity
- uniform distribution
- vc dimension
- learning curves
- learning algorithm
- machine learning algorithms
- theoretical analysis
- satisfiability problem
- np complete
- np hard
- competitive ratio
- high dimensional