Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity.

Yanyi Liu Rafael Pass

Published in: CCC (2022)

Keyphrases

kolmogorov complexity
inductive inference
complexity measures
np complete
phase transition
computational complexity
np hard
information theoretic
learning theory
neural network
genetic algorithm
training data
worst case
machine learning algorithms
agnostic learning