Computer Science/Discrete Mathematics Seminar II

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. The analysis of this (very analytic) algorithm crucially uses recent results in invariant theory. Exploring the power of these new algorithms seem to be promising. They efficiently solve a large family of non-convex optimization problems, as well as a large family of linear programs with exponentially many facets. In particular, these capture matroid intersection, and raise the question of which other natural optimization problems can be reduced to them. No prior knowledge will be assumed. Joint work with Ankit Garg, Leonid Gurvits and Rafael Olivera.