Theory Lunch This Week (12:00, 11/21, GHC 502C)

[Grayson York]

Hi all,

Please join us for our first theory lunch in the new building this Thursday at noon in the 5th floor conference room of Ginsburg. Only PhD students and Faculty will have card access to the upper floors of the building, so please send me an email (grayso...@gmail.com) when you arrive if you are unable to access the upper floors so that we can let you in. Our speaker this week will be Professor Aravind Srinivasan, who is visiting from the University of Maryland, College Park. He will be presenting the following paper:

Title: Concentration of Submodular Functions and Read-k Families Under Negative Dependence


Abstract: We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We prove such a concentration inequality for the lower tail when the random variables satisfy negative association or negative regression, partially resolving an open problem raised by Qiu and Singla. Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms (Chekuri-Vondrak-Zenklusen and Harvey-Olver). We also show applications to the concentration of “read-k” families (Gavinsky et al.) under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of Gavinsky et al.


This is joint work with Sharmila Duppala, George Z. Li, Juan Luque, and Renata Valieva that will appear at ITCS 2025.

[Grayson York]

please join us at the following zoom link:

https://usc.zoom.us/j/99364768001?pwd=XKU8LWP3gBbwkDkeOll6qXX3uvOZZA.1