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 in (Qiu and Singla [QS22]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms (Chekuri, Vondrak, and Zenklusen [CVZ10] and Harvey and Olver [HO14]). We further show a simplified proof of the entropy-method approach of [Gav+15], and discuss applications of our results to the concentration of read-k families under negative dependence.
Renata is a fourth year PhD student at the University of Maryland, College Park, advised by Aravind Srinivasan. Her interests lie in the design and analysis of randomized algorithms, with a focus in dependent rounding and concentration inequalities.