Entropy of weight distributions of small-bias spaces and pseudobinomiality

DOI10.1007/978-3-319-21398-9_39MaRDI QIDQ3196409zbMATH OpenOpenAlexFDO

Authors Louay Bazzi

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.5681

zbMATH Keywords

Shannon entropyFourier analysispseudorandomnesssmall-biaspseudobinomiality

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Measures of information, entropy (94A17)

Abstract: The bilateral minimum distance of a binary linear code is the maximum $d$ such that all nonzero codewords have weights between $d$ and $n-d$. Let $Qsubset{0,1}^n$ be a binary linear code whose dual has bilateral minimum distance at least $d$, where $d$ is odd. Roughly speaking, we show that the average $L_{i}nfty$-distance -- and consequently the $L_1$-distance -- between the weight distribution of a random cosets of $Q$ and the binomial distribution decays quickly as the bilateral minimum distance $d$ of the dual of $Q$ increases. For $d=Theta(1)$, it decays like $n^{-Theta(d)}$. On the other $d=Theta(n)$ extreme, it decays like and $e^{-Theta(d)}$. It follows that, almost all cosets of $Q$ have weight distributions very close to the to the binomial distribution. In particular, we establish the following bounds. If the dual of $Q$ has bilateral minimum distance at least $d=2t+1$, where $tgeq1$ is an integer, then the average $L_{i}nfty$-distance is at most $minleft(elnfracn2tight{)}^{t}left(frac2tnight{)}^{fract2},sqrt2e^{-fract10}$. For the average $L_1$-distance, we conclude the bound $min(2t+1)left(elnfracn2tight{)}^{t}left(frac2tnight{)}^{fract2-1},sqrt2(n+1)e^{-fract10}$, which gives nontrivial results for $tgeq3$. We given applications to the weight distribution of cosets of extended Hadamard codes and extended dual BCH codes. Our argument is based on Fourier analysis, linear programming, and polynomial approximation techniques.

Recommendations

• Entropy of weight distributions of small-bias spaces and pseudobinomiality
• Some limitations of the sum of small-bias distributions
• Small-bias is not enough to hit read-once CNF
• Approximating probability distributions using small sample spaces
• Small-Bias Probability Spaces: Efficient Constructions and Applications

Cites work

• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• Approximating probability distributions using small sample spaces
• Elements of Information Theory
• Entropy computations via analytic depoissonization
• Entropy of weight distributions of small-bias spaces and pseudobinomiality
• Explicit construction of a small epsilon-net for linear threshold functions
• Hardness vs randomness
• Improved pseudorandom generators for depth 2 circuits
• Pseudorandom Bit Generators That Fool Modular Sums
• Pseudorandom generators for combinatorial shapes
• Pseudorandom generators for space-bounded computation
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Small-Bias Spaces for Group Products

Cited in

(2)

• Entropy of weight distributions of small-bias spaces and pseudobinomiality
• Entropy of weight distributions of small-bias spaces and pseudobinomiality

This page was built for publication: Entropy of weight distributions of small-bias spaces and pseudobinomiality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196409)