Talk: On Algorithmic Aspects of Brascamp-Lieb Inequalities

Thursday, August 4, 2016 - 4:00pm to 5:00pm
Ankit Garg
Microsoft Research

The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory. While their structural theory is very well understood, far less is known about computing their main parameters. We give polynomial time algorithms to compute:

- Feasibility of BL-datum

- The optimal BL-constant

-  A weak separation oracle for the BL-polytope

This will be based on joint work with Leonid Gurvits, Rafael Oliveira and Avi Wigderson.

The algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by Gurvits, for which the present authors provided a polynomial time algorithm recently.