Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity.

Yanyi Liu Rafael Pass

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

Keyphrases

average case
kolmogorov complexity
worst case
inductive inference
uniform distribution
worst case analysis
vc dimension
upper bound
learning curves
lower bound
computational complexity
complexity measures
phase transition
average case complexity
np hard
data sets
learning theory
image quality
pairwise