A short note on the joint entropy of n/2-wise independence

09/03/2017
by   Amey Bhangale, et al.
0

In this note, we prove a tight lower bound on the joint entropy of n unbiased Bernoulli random variables which are n/2-wise independent. For general k-wise independence, we give new lower bounds by adapting Navon and Samorodnitsky's Fourier proof of the `LP bound' on error correcting codes. This counts as partial progress on a problem asked by Gavinsky and Pudlák.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset