Paper Info
Title
A short note on the joint entropy of n/2-wise independence.
Abstract
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 Samorodnitskyu0027s Fourier proof of the `LP boundu0027 on error correcting codes. This counts as partial progress on a problem asked by Gavinsky and Pudlu0027ak.
Year
Venue
Field
2017
arXiv: Discrete Mathematics
Discrete mathematics,Combinatorics,Random variable,Upper and lower bounds,Fourier transform,Joint entropy,Mathematics,Bernoulli's principle
DocType
Volume
Citations 
Journal
abs/1709.00752
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
Amey Bhangale1106.71
Aditya Potukuchi213.07