Overview

Probability distributions are fundamental to many algorithms, but high-dimensional distributions can be represented in various ways: as empirical distributions with samples, through probability density functions, or via samplers that generate conditional samples. Learning a generative model from a dataset can in fact be seen as transforming an empirical distribution into a parameterized representation. This talk explores how the computational complexity of working with distributions depends on their representations. First I discuss previous work with Saeed Mahloujifar and Mohammad Mahmoody, in which an algorithmic version of the “concentration of measure” phenomenon in high dimensions is shown to be computable in polynomial time under a natural representation. Next I talk about continuing research on algorithmic variants of optimal transport between high-dimensional probability spaces. The only requirement for some algorithms to work is a representation of the distribution that is available naturally for some generative models like Large Language Models (LLMs). We finish the talk with some open questions.