A Note on the Joint Entropy of N/2-Wise Independence

In this note, we prove a tight lower bound on the joint entropy of <tex>$n$</tex> unbiased Bernoulli random variables which are <tex>$n$</tex>/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 Pudlak in [3].

• Publication year

  2018

• Venue

  International Symposium on Information Theory

• Publication date

  2018-06-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ISIT.2018.8437849
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Joint Entropy of $d$-Wise-Independent Variables

  2015cited by this paper
• Entropy Versus Pairwise Independence

  2013cited by this paper
• Linear Programming Bounds for Codes via a Covering Argument

  2007influential reference
• The Probabilistic Method

  1998cited by this paper
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities

  1977cited by this paper

• No citing papers are available for this paper.