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

Yanyi Liu Rafael Pass

Published in: Electron. Colloquium Comput. Complex. (2023)

Keyphrases

worst case
kolmogorov complexity
np hard
inductive inference
lower bound
average case
error bounds
greedy algorithm
upper bound
loss bounds
continuous functions
running times
approximation algorithms
data mining
learning theory