Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-051 | 25th April 2012 03:04

#### A Tail Bound for Read-k Families of Functions

TR12-051
Authors: Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan
Publication: 27th April 2012 16:59
Downloads: 1183
Keywords:

Abstract:

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables \$Y_1,\ldots,Y_r\$ are arbitrary Boolean functions of independent random variables \$X_1,\ldots,X_m\$, modulo a restriction that every \$X_i\$ influences at most \$k\$ of the variables \$Y_1,\ldots,Y_r\$.

ISSN 1433-8092 | Imprint