A tail bound for read‐k families of functions1. Issue 1 (6th March 2014) - Gavinsky, Dmitry
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 Y1, …, Yr are arbitrary [0, 1]‐valued functions of independent random variables X1, …, Xm, modulo a restriction that every Xi influences at most k of the variables Y1, …, Yr. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 99–108, 2015