License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17137/
Go to the corresponding LIPIcs Volume Portal

Skorski, Maciej

Tight Chernoff-Like Bounds Under Limited Independence

pdf-format:
LIPIcs-APPROX15.pdf (0.8 MB)

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
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI