t-Wise independence with local dependencies

Ronen Gradwohl; Amir Yehudayoff

doi:10.1016/j.ipl.2007.11.010

t-Wise independence with local dependencies

Ronen Gradwohl^*, Amir Yehudayoff

^*Corresponding author for this work

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	208-212
Number of pages	5
Journal	Information Processing Letters
Volume	106
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2007.11.010
State	Published - May 31 2008

Funding

* Corresponding author. E-mail addresses: [email protected] (R. Gradwohl), [email protected] (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.

Keywords

Combinatorial problems
Large deviation bounds
Limited independence

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2007.11.010

Cite this

@article{0cc10482910a4f9cbd34e26659babbfd,

title = "t-Wise independence with local dependencies",

abstract = "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.",

keywords = "Combinatorial problems, Large deviation bounds, Limited independence",

author = "Ronen Gradwohl and Amir Yehudayoff",

note = "Funding Information: * Corresponding author. E-mail addresses: [email protected] (R. Gradwohl), [email protected] (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.",

year = "2008",

month = may,

day = "31",

doi = "10.1016/j.ipl.2007.11.010",

language = "English (US)",

volume = "106",

pages = "208--212",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - t-Wise independence with local dependencies

AU - Gradwohl, Ronen

AU - Yehudayoff, Amir

N1 - Funding Information: * Corresponding author. E-mail addresses: [email protected] (R. Gradwohl), [email protected] (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 -

t-Wise independence with local dependencies

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this