Weakly biased arrays, almost independent arrays and error-correcting codes (Q2717192)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Weakly biased arrays, almost independent arrays and error-correcting codes |
scientific article; zbMATH DE number 1604770
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Weakly biased arrays, almost independent arrays and error-correcting codes |
scientific article; zbMATH DE number 1604770 |
Statements
9 December 2002
0 references
limited bias
0 references
\(\epsilon\)-biased arrays
0 references
\(\epsilon\)-biased functions
0 references
\(\epsilon\)-biased random variables
0 references
random variables
0 references
codes
0 references
expander graphs
0 references
Fourier transform
0 references
limited dependences
0 references
\(\epsilon\)-dependent arrays
0 references
0.8595773
0 references
0.8573497
0 references
0.8555981
0 references
0.8543782
0 references
0.8533763
0 references
0.8528459
0 references
0.85227615
0 references
Weakly biased arrays, almost independent arrays and error-correcting codes (English)
0 references
The basic notions of limited bias and limited dependences from the coding-theoretic point of view are analysed. This leads to a simplification of the constructions from [\textit{N. Alon, O. Goldreich, J. Håstad}, and \textit{R. Peralta}, Random Struct. Algorithms 3, 289-304 (1992; Zbl 0755.60002) and \textit{J. Naor} and \textit{M. Naor}, SIAM J. Comput. 22, 838-856 (1993; Zbl 0776.60014)] of families of random variables with the prescribed independence properties defined on a small sample space. This is the main result of the paper, expressed in coding-theoretic language. The applications comprise universal hashing, authentication, resilient functions and pseudorandomness.NEWLINENEWLINEFor the entire collection see [Zbl 0960.00079].
0 references
