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

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

Published in: IACR Cryptol. ePrint Arch. (2020)

Keyphrases

average case
worst case
worst case analysis
uniform distribution
learning curves
average case complexity
computational complexity
upper bound
machine learning
lower bound
agnostic learning