t-Wise Independence with Local Dependencies

Ronen Gradwohl, Amir Yehudayoff

In this note we prove a large deviation bound on the sum of random variables with the following dependency structure: there is a dependency graph $G$ with a bounded chromatic numbe…