Chennai Mathematical Institute

Seminars




10:30 am., Seminar Hall
Algorithmic and optimization aspects of Brascamp-Lieb inequalities

Ankit Garg
MSR, New England.
16-02-17


Abstract

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

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. If time permits, I will briefly describe the connection to invariant theory of quiver representations which is crucial for the analysis of our algorithm.

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





Google
Search WWW Search cmi.ac.in