TY - JOUR
T1 - t-Wise independence with local dependencies
AU - Gradwohl, Ronen
AU - Yehudayoff, Amir
N1 - Funding Information:
* Corresponding author. E-mail addresses: ronen.gradwohl@weizmann.ac.il (R. Gradwohl), amir.yehudayoff@weizmann.ac.il (A. Yehudayoff). 1 Research supported by US–Israel Binational Science Foundation Grant 2006060. 2 Research supported by a grant from the Israel Ministry of Science (IMOS)—Eshkol Fellowship.
PY - 2008/5/31
Y1 - 2008/5/31
N2 - 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 number, in which each vertex represents a random variable. Variables that are represented by neighboring vertices may be arbitrarily dependent, but collections of variables that form an independent set in G are t-wise independent.
AB - 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 number, in which each vertex represents a random variable. Variables that are represented by neighboring vertices may be arbitrarily dependent, but collections of variables that form an independent set in G are t-wise independent.
KW - Combinatorial problems
KW - Large deviation bounds
KW - Limited independence
UR - http://www.scopus.com/inward/record.url?scp=41549161693&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=41549161693&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2007.11.010
DO - 10.1016/j.ipl.2007.11.010
M3 - Article
AN - SCOPUS:41549161693
SN - 0020-0190
VL - 106
SP - 208
EP - 212
JO - Information Processing Letters
JF - Information Processing Letters
IS - 5
ER -