2016/07/22 by Ankit Garg, Garg, Ankit, Leonid Gurvits +6 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #Classical Analysis and ODEs (math.CA) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #Probabilistic and Robust Engineering Design
paper · pdf · doi:10.48550/arxiv.1607.06711
openalex publication_date 2016/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an\nimportant mathematical tool, unifying and generalizing numerous inequalities in\nanalysis, convex geometry and information theory. While their structural theory\nis very well understood, far less is known about computing their main\nparameters.\n We give polynomial time algorithms to compute feasibility of BL-datum, the\noptimal BL-constant and a weak separation oracle for the BL-polytope. The same\nresult holds for the so-called Reverse BL inequalities of Barthe. The best\nknown algorithms for any of these tasks required at least exponential time.\n The algorithms are obtained by a simple efficient reduction of a given\nBL-datum to an instance of the Operator Scaling problem defined by Gurvits, for\nwhich the present authors have provided a polynomial time algorithm. This\nreduction implies algorithmic versions of many of the known structural results,\nand in some cases provide proofs that are different or simpler than existing\nones.\n Of particular interest is the fact that the operator scaling algorithm is\ncontinuous in its input. Thus as a simple corollary of our reduction we obtain\nexplicit bounds on the magnitude and continuity of the BL-constant in terms of\nthe BL-data. To the best of our knowledge no such bounds were known, as past\narguments relied on compactness. The continuity of BL-constants is important\nfor developing non-linear BL inequalities that have recently found so many\napplications.\n