### DIMACS Theory of Computing Seminar

Title: Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities

Speaker: **Ankit Garg**, Princeton University

Date: Wednesday, December 7, 2016 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

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.

Based on joint work with Leonid Gurvits, Rafael Oliveira and Avi Wigderson.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/