Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling
Ankit K. Garg, Leonid I Gurvits, Rafael Oliveira, Avi Wigderson · 2017
The celebrated Brascamp-Lieb (BL) inequalities [BL76, Lie90], and their reverse form of Barthe [Bar98], are an important mathematical tool, unifying and generalizing numerous in- equalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters below (which we later define). Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute: