Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity.

Yanyi Liu Rafael Pass

Published in: STOC (2021)

Keyphrases

average case
kolmogorov complexity
worst case
inductive inference
vc dimension
uniform distribution
worst case analysis
learning curves
computational complexity
upper bound
lower bound
np hard
complexity measures
average case complexity
phase transition
learning theory
pac learning
machine learning