pith. sign in

arxiv: 1709.00752 · v2 · pith:BV4HWC77new · submitted 2017-09-03 · 💻 cs.DM · math.CO· math.PR

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

classification 💻 cs.DM math.COmath.PR
keywords wiseboundentropyindependencejointlowernoteadapting
0
0 comments X
read the original 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 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\'ak.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.