Root of Polynomials, Generalized Log-Concavity and Algorithmic Applications
Time: 2024-06-19
Published By: Wenqiong Li
Speaker(s): Thuy-Duong Vuong (Stanford University)
Time: 14:00-15:00 July 17, 2024
Venue: Room 77201, Jingchunyuan 78, BICMR
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.
