Topic: universality

Michal Dereziński discusses oblivious subspace embeddings, random dimension-reduction maps that approximately preserve all vector norms in a low-dimensional subspace. Such maps support least-squares regression and low-rank approximation, yet efficient optimal embedding dimensions have left a gap between theory and practice. Analyzing universality in sparse random matrices leads to a resolution of the Nelson–Nguyen conjecture up to sub-polylogarithmic factors in SODA 2026. Joint work with Shabarish Chenakkod, Xiaoyu Dong, and Mark Rudelson.

It is sometimes said that there are two reasons why physics is so successful as a science. One is that it deals with very simple problems. The other is that it attempts to account only for universal aspects of systems at a desired level of description, with lower level phenomena subsumed into a small number of adjustable parameters. It is a widespread belief that this approach seems unlikely to be useful in biology, which is intimidatingly complex, where “everything has an exception”, and where there are a huge number of undetermined parameters. I will try to argue, nonetheless, that there are