Non-Black-Box Worst-Case to Average-Case Reductions within NP.
Shuichi HiraharaPublished in: FOCS (2018)
Keyphrases
- black box
- average case
- worst case
- np hard
- computational complexity
- worst case analysis
- learning curves
- black boxes
- white box
- lower bound
- uniform distribution
- upper bound
- hybrid systems
- approximation algorithms
- test cases
- greedy algorithm
- vc dimension
- sample size
- average case complexity
- machine learning
- white box testing
- np hardness
- objective function