Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\).

Shuichi Hirahara

Published in: SIAM J. Comput. (2023)

Keyphrases

black box
average case
worst case
np hard
computational complexity
black boxes
worst case analysis
learning curves
white box
greedy algorithm
integration testing
uniform distribution
approximation algorithms
test cases
sample size
hybrid systems
upper bound
lower bound
sample complexity
machine learning
databases