{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T05:44:45Z","timestamp":1777355085220,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T00:00:00Z","timestamp":1771200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T00:00:00Z","timestamp":1771200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CF-1918749"],"award-info":[{"award-number":["CF-1918749"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    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 ([1]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([2, 3]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read-\n                    <jats:italic>k<\/jats:italic>\n                    families [4] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [4].\n                  <\/jats:p>","DOI":"10.1007\/s00453-026-01372-w","type":"journal-article","created":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T09:58:22Z","timestamp":1771235902000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Concentration of Submodular Functions and Read-k Families Under Negative Dependence"],"prefix":"10.1007","volume":"88","author":[{"given":"Sharmila","family":"Duppala","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George Z.","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Luque","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renata","family":"Valieva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,16]]},"reference":[{"key":"1372_CR1","doi-asserted-by":"publisher","unstructured":"Qiu, F., Singla, S.: Submodular dominance and applications. In: Chakrabarti, A., Swamy, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2022. LIPIcs, vol. 245, pp. 44\u201314421. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, ??? (2022). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2022.44","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.44"},{"key":"1372_CR2","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 575\u2013584. IEEE Computer Society, ??? (2010). https:\/\/doi.org\/10.1109\/FOCS.2010.60","DOI":"10.1109\/FOCS.2010.60"},{"key":"1372_CR3","doi-asserted-by":"publisher","unstructured":"Harvey, N.J.A., Olver, N.: Pipage rounding, pessimistic estimators and matrix concentration. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 926\u2013945. SIAM, ??? (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.69","DOI":"10.1137\/1.9781611973402.69"},{"issue":"1","key":"1372_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/rsa.20532","volume":"47","author":"D Gavinsky","year":"2015","unstructured":"Gavinsky, D., Lovett, S., Saks, M.E., Srinivasan, S.: A tail bound for read-$$k$$ families of functions. Random Struct. Algorithms 47(1), 99\u2013108 (2015). https:\/\/doi.org\/10.1002\/rsa.20532","journal-title":"Random Struct. Algorithms"},{"key":"1372_CR5","volume-title":"The Probabilistic Method, Third Edition. Wiley-Interscience series in discrete mathematics and optimization","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, Third Edition. Wiley-Interscience series in discrete mathematics and optimization. Wiley, ??? (2008)"},{"key":"1372_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, ??? (2009). (http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item2327542\/)"},{"issue":"4","key":"1372_CR7","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff, H.: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations. Ann. Math. Stat. 23(4), 493\u2013507 (1952). https:\/\/doi.org\/10.1214\/aoms\/1177729330","journal-title":"Ann. Math. Stat."},{"issue":"301","key":"1372_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"issue":"3","key":"1372_CR9","doi-asserted-by":"publisher","first-page":"357","DOI":"10.2748\/tmj\/1178243286","volume":"19","author":"K Azuma","year":"1967","unstructured":"Azuma, K.: Weighted sums of certain dependent random variables. Tohoku Math. J. 19(3), 357\u2013367 (1967). https:\/\/doi.org\/10.2748\/tmj\/1178243286","journal-title":"Tohoku Math. J."},{"issue":"2","key":"1372_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"JP Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-hoeffding bounds for applications with limited independence. SIAM J. Discret. Math. 8(2), 223\u2013250 (1995). https:\/\/doi.org\/10.1137\/S089548019223872X","journal-title":"SIAM J. Discret. Math."},{"key":"1372_CR11","doi-asserted-by":"publisher","unstructured":"Skorski, M.: Tight chernoff-like bounds under limited independence. In: Chakrabarti, A., Swamy, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2022. LIPIcs, vol. 245, pp. 15\u201311514. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, ??? (2022). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2022.15","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.15"},{"issue":"3","key":"1372_CR12","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324\u2013360 (2006). https:\/\/doi.org\/10.1145\/1147954.1147956","journal-title":"J. ACM"},{"issue":"2","key":"1372_CR13","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997). https:\/\/doi.org\/10.1137\/S0097539793250767","journal-title":"SIAM J. Comput."},{"key":"1372_CR14","unstructured":"Garbe, K., Vondr\u00e1k, J.: Concentration of Lipschitz Functions of Negatively Dependent Variables (2018)"},{"key":"1372_CR15","doi-asserted-by":"publisher","unstructured":"Srinivasan, A.: Distributions on level-sets with applications to approximation algorithms. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, pp. 588\u2013597. IEEE Computer Society, ??? (2001). https:\/\/doi.org\/10.1109\/SFCS.2001.959935","DOI":"10.1109\/SFCS.2001.959935"},{"key":"1372_CR16","doi-asserted-by":"publisher","unstructured":"Peres, Y., Singh, M., Vishnoi, N.K.: Random walks in polytopes and negative dependence. In: Papadimitriou, C.H. (ed.) 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA. LIPIcs, vol. 67, pp. 50\u201315010. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, ??? (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.50","DOI":"10.4230\/LIPIcs.ITCS.2017.50"},{"key":"1372_CR17","unstructured":"Udwani, R.: Multi-objective maximization of monotone submodular functions with cardinality constraint. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Annual Conference on Neural Information Processing Systems, NeurIPS 2018, pp. 9513\u20139524 (2018). https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/7e448ed9dd44e6e22442dac8e21856ae-Abstract.html"},{"key":"1372_CR18","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Quanrud, K.: Submodular function maximization in parallel via the multilinear relaxation. In: Chan, T.M. (ed.) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 303\u2013322. SIAM, ??? (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.20","DOI":"10.1137\/1.9781611975482.20"},{"key":"1372_CR19","doi-asserted-by":"publisher","unstructured":"Allen-Zhu, Z., Orecchia, L.: Nearly-linear time positive lp solver with faster convergence rate. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC \u201915, pp. 229\u2013236. Association for Computing Machinery, ??? (2015). https:\/\/doi.org\/10.1145\/2746539.2746573","DOI":"10.1145\/2746539.2746573"},{"key":"1372_CR20","doi-asserted-by":"publisher","unstructured":"Tsang, A., Wilder, B., Rice, E., Tambe, M., Zick, Y.: Group-fairness in influence maximization. In: Kraus, S. (ed.) Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, pp. 5997\u20136005. ijcai.org, ??? (2019). https:\/\/doi.org\/10.24963\/ijcai.2019\/831","DOI":"10.24963\/ijcai.2019\/831"},{"key":"1372_CR21","unstructured":"Wajc, D.: Negative Association: Definition, Properties, and Applications. Manuscript (2017). https:\/\/www.cs.cmu.edu\/$$\\sim $$dwajc\/notes\/Negative%20Association.pdf"},{"issue":"2","key":"1372_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D Dubhashi","year":"1998","unstructured":"Dubhashi, D., Ranjan, D.: Balls and bins: a study in negative dependence. Random Struct. Algorithms 13(2), 99\u2013124 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"1372_CR23","doi-asserted-by":"publisher","unstructured":"Feder, T., Mihail, M.: Balanced matroids. In: Kosaraju, S.R., Fellows, M., Wigderson, A., Ellis, J.A. (eds.) Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992, pp. 26\u201338. ACM, ??? (1992). https:\/\/doi.org\/10.1145\/129712.129716","DOI":"10.1145\/129712.129716"},{"key":"1372_CR24","doi-asserted-by":"publisher","unstructured":"Karlin, A.R., Klein, N., Gharan, S.O.: A (slightly) improved approximation algorithm for metric TSP. In: Khuller, S., Williams, V.V. (eds.) STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 32\u201345. ACM, ??? (2021). https:\/\/doi.org\/10.1145\/3406325.3451009","DOI":"10.1145\/3406325.3451009"},{"key":"1372_CR25","unstructured":"Naor, J.S., Srinivasan, A., Wajc, D.: Online Dependent Rounding Schemes. https:\/\/arxiv.org\/abs\/2301.08680"},{"key":"1372_CR26","doi-asserted-by":"crossref","unstructured":"Newman, C.M.: Asymptotic independence and limit theorems for positively and negatively dependent random variables. Lecture Notes-Monograph Series 5, 127\u2013140 (1984). Accessed 2023-09-03","DOI":"10.1214\/lnms\/1215465639"},{"issue":"1","key":"1372_CR27","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1017\/S0963548313000345","volume":"23","author":"R Pemantle","year":"2014","unstructured":"Pemantle, R., Peres, Y.: Concentration of lipschitz functionals of determinantal and other strong rayleigh measures. Comb. Probab. Comput. 23(1), 140\u2013160 (2014). https:\/\/doi.org\/10.1017\/S0963548313000345","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"1372_CR28","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1090\/S0894-0347-08-00618-8","volume":"22","author":"J Borcea","year":"2009","unstructured":"Borcea, J., Br\u00e4nd\u00e9n, P., Liggett, T.M.: Negative dependence and the geometry of polynomials. J. Am. Math. Soc. 22(2), 521\u2013567 (2009)","journal-title":"J. Am. Math. Soc."},{"issue":"3","key":"1372_CR29","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s004930070014","volume":"20","author":"JH Kim","year":"2000","unstructured":"Kim, J.H., Vu, V.H.: Concentration of multivariate polynomials and its applications. Comb. 20(3), 417\u2013434 (2000). https:\/\/doi.org\/10.1007\/s004930070014","journal-title":"Comb."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01372-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01372-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01372-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T05:01:48Z","timestamp":1777352508000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01372-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,16]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1372"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01372-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,16]]},"assertion":[{"value":"8 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Funding: All authors were supported in part by NSF award number CCF-1918749. Employment: Affiliation with University of Maryland, College Park, and Carnegie Mellon University","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"21"}}