2026-07-23T08:35:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22675 2026-04-17T05:32:10Z ddc:004 open_access

Concentration of Submodular Functions and Read-k Families Under Negative Dependence Duppala, Sharmila Li, George Z. Luque, Juan Srinivasan, Aravind Valieva, Renata Chernoff bounds Submodular Functions Negative Correlation 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 ([Frederick Qiu and Sahil Singla, 2022]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([Chandra Chekuri et al., 2010; Nicholas J. A. Harvey and Neil Olver, 2014]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read-k families [Dmitry Gavinsky et al., 2015] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [Dmitry Gavinsky et al., 2015]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sharmila Duppala and George Z. Li and Juan Luque and Aravind Srinivasan and Renata Valieva 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.47 urn:nbn:de:0030-drops-226751 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.47 eng https://creativecommons.org/licenses/by/4.0/legalcode