The idea that learning is closely tied to compression has long served as both a powerful principle and,
at times, an informal analogy across machine learning and learning theory. Here we focus on settings in
which that intuition can be made mathematically precise, surveying formal connections among learning
algorithms, data compression, and computational complexity theory, with an emphasis on recent progress
and current frontiers. We describe how techniques from complexity theory can guide the design of
both supervised and unsupervised learning algorithms with provable guarantees, and conversely, how
learning algorithms can yield new insights and results in complexity theory. A central theme is the
role of data compression as a bridge between learning and complexity, especially through an area called
meta-complexity, which studies the computational difficulty of compression problems and time-bounded
variants of Kolmogorov complexity.