Tight Chernoff-Like Bounds Under Limited Independence

Maciej Skorski

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 p…