Some Results on Average-Case Hardness Within the Polynomial Hierarchy.
Aduri PavanRahul SanthanamN. V. VinodchandranPublished in: FSTTCS (2006)
Keyphrases
- average case
- polynomial hierarchy
- worst case
- phase transition
- dnf formulas
- uniform distribution
- np hard
- answer sets
- upper bound
- lower bound
- np complete
- vc dimension
- np hardness
- sample size
- machine learning
- concept class
- constraint satisfaction
- semi supervised
- computational complexity
- metric space
- pac learning
- special case
- dl lite
- decision trees
- learning algorithm