A tail bound for read-k families of functions

Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)99-108
Number of pages10
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Aug 1 2015

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


  • Chernoff bounds
  • Information theory
  • Limited independence
  • Shearer's lemma


Dive into the research topics of 'A tail bound for read-k families of functions'. Together they form a unique fingerprint.

Cite this