Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity.

Yanyi Liu Rafael Pass

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

Keyphrases

kolmogorov complexity
inductive inference
complexity measures
learning theory
np hard
phase transition
computational complexity
neural network
worst case
information theoretic
feature space
special case
intelligent systems
np hardness
agnostic learning