Root of Polynomials, Generalized Log-Concavity and Algorithmic Applications
发布时间：2024年06月19日
浏览次数：768
发布者: Wenqiong Li
主讲人： Thuy-Duong Vuong (Stanford University)
活动时间： 从 2024-07-17 14:00 到 15:00
场地： 北京国际数学研究中心，镜春园78号院（怀新园）77201室
In this talk, we explore the connection between the root-freeness and fractional log-concavity of the generating polynomial of discrete distribution. Fractional log-concavity is an analog to the Lorentzian [Branden-Huh’19]/log-concavity [Anari-Liu-OveisGharan-Vinzant’19] property of the generating polynomials of matroids. We show that multivariate generating polynomials without roots in a sector of the complex plane are fractionally log-concave. As an application, we show how fractional log-concavity implies efficient algorithms for sampling and optimization.” Based on joint works with Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur.
