Pseudorandomness Seminar

A Gentle Introduction to Brascamp-Lieb Inequalities and Why I Like Them

The celebrated Brascamp-Lieb (BL) inequalities  are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters. Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute them. In particular, these efficiently solve a large family of linear programs with exponentially many facets, something which can be used for combinatorial optimization. Both algorithms and analysis rely on our previous Operator Scaling algorithm, and combine interesting math from several diverse fields. However, no prior knowledge will be assumed for this talk.
Joint work with Ankit Garg, Leonid Gurvits and Rafael Olivera