Avi Wigderson: Structural and computational aspects of Brascamp-Lieb inequalities
Time: Wed 2017-05-24 10.15 - 11.15
Location: Room 3418, Lindstedtsvägen 25. Department of Mathematics, KTH
Participating: Avi Wigderson, Institute for Advanced Study, Princeton
Abstract
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.
I will survey the well-understood structural theory of BL inequalities,
and then discuss their computational aspects. Far less was known about
computing their main parameters, and I will discuss new efficient
algorithms (via operator scaling) for those, which also inform
structural questions. In particular, these efficiently solve a large
family of linear programs with exponentially many facets, potentially
useful for combinatorial optimization. The analysis of this (very
analytic) algorithm crucially uses modern results in invariant theory.
No prior knowledge from previous talks will be assumed. Joint work with
Ankit Garg, Leonid Gurvits and Rafael Olivera