Entropy of weight distributions of small-bias spaces and pseudobinomiality

DOI10.1007/978-3-319-21398-9_39zbMATH Open1397.94032arXiv1408.5681OpenAlexW2283539335MaRDI QIDQ3196409FDOQ3196409

Louay Bazzi

Publication date: 29 October 2015

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

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.

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

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

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)

Cites Work

• Elements of Information Theory
• Hardness vs randomness
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Simple Constructions of Almost k-wise Independent Random Variables
• Entropy computations via analytic depoissonization
• Title not available (Why is that?)
• Pseudorandom Bit Generators That Fool Modular Sums
• Improved Pseudorandom Generators for Depth 2 Circuits
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators for combinatorial shapes
• Small-Bias Spaces for Group Products
• Approximating probability distributions using small sample spaces
• Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality
• Explicit construction of a small epsilon-net for linear threshold functions

Cited In (1)

• 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)