Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions.

Shuichi Hirahara

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

Keyphrases

kolmogorov complexity
inductive inference
complexity measures
computational complexity
learning theory
database
active learning
np complete
data sets
worst case
graphical models
information theoretic
learning problems
phase transition