Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.

Ruiwen Chen Rahul Santhanam Srikanth Srinivasan

Published in: Theory Comput. (2018)

Keyphrases

average case
worst case
lower bound
worst case analysis
online algorithms
average case complexity
computational complexity
upper bound
uniform distribution
vc dimension
competitive ratio
learning algorithm
objective function
satisfiability problem
model selection
active learning
optimal solution