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 ... more >>>

A constant-depth circuit consists of AND and OR gates of unbounded fan-in, arranged in a constant number of layers, that read the input literals; for example, a depth-three circuit is an OR of CNFs or an AND of DNFs. The classical lower bound of Håstad (1989) states that every depth-$d$ ... more >>>

We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents. The central ingredient is selected-entry matrix multiplication: computing a prescribed set of entries of a product of dense rectangular matrices. Starting from Sch\"onhage's inner/outer-product ... more >>>