Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.15
URN: urn:nbn:de:0030-drops-171372
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17137/
Skorski, Maciej
Tight Chernoff-Like Bounds Under Limited Independence
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{skorski:LIPIcs.APPROX/RANDOM.2022.15,
author = {Skorski, Maciej},
title = {{Tight Chernoff-Like Bounds Under Limited Independence}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {15:1--15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-249-5},
ISSN = {1868-8969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17137},
URN = {urn:nbn:de:0030-drops-171372},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.15},
annote = {Keywords: concentration inequalities, tail bounds, limited independence, k-wise independence}
}
| Keywords: | concentration inequalities, tail bounds, limited independence, k-wise independence | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 15.09.2022 |
