On Average-Case Hardness in TFNP from One-Way Functions.

Pavel Hubácek Chethan Kamath Karel Král Veronika Slívová

Published in: TCC (3) (2020)

Keyphrases

average case
worst case
uniform distribution
worst case analysis
learning curves
vc dimension
np hard
learning curve
upper bound
phase transition
pac learning