Take Action

Home | Faculty & Research Overview | Research

Research Details

t-Wise Independence with Local Dependencies, Information Processing Letters

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.

Type

Article

Author(s)

Ronen Gradwohl, Amir Yehudayoff

Date Published

2008

Citations

Gradwohl, Ronen, and Amir Yehudayoff. 2008. t-Wise Independence with Local Dependencies. Information Processing Letters. 106: 208-212.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more

Take Action