On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity.

Yanyi Liu Rafael Pass

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

Keyphrases

worst case
kolmogorov complexity
np hard
inductive inference
average case
greedy algorithm
upper bound
continuous functions
error bounds
complexity measures
approximation algorithms
computational complexity
running times
lower bound
data mining
space complexity
basis functions
labeled data
artificial neural networks