School of Technology and Computer Science Seminars

Entropy Versus Pairwise Independence

by Varun Narayanan (School of Technology and Computer Science, TIFR)

Friday, November 10, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
We would discuss the lower bound on the joint entropy of pairwise independent random variables (X_1, ... , X_n) by Lazlo Babai (2013). We know that 2^n - 1 pairwise independent balanced Bernoulli r.v's can be constructed using n independent Bernoulli r.v's. This lower bound shows that this is the best we can do up to a constant factor.