10:30 am., Seminar Hall
Algorithmic and optimization aspects of Brascamp-Lieb inequalities
MSR, New England.
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 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