2026-07-23T22:19:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17137 2024-03-06T10:59:03Z ddc:004 open_access

Tight Chernoff-Like Bounds Under Limited Independence Skorski, Maciej concentration inequalities tail bounds limited independence k-wise independence This paper develops sharp bounds on moments of sums of k-wise independent bounded random variables, under constrained average variance. The result closes the problem addressed in part in the previous works of Schmidt et al. and Bellare, Rompel. The work also discusses other applications of independent interests, such as asymptotically sharp bounds on binomial moments. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maciej Skorski 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.15 urn:nbn:de:0030-drops-171372 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.15 eng https://creativecommons.org/licenses/by/4.0/legalcode