Small-bias Probability Spaces: efficient constructions and Applications

Noga Alon Shuki Bruck Joseph Naor Moni Naor Ronny Roth

Abstract:

A new technique, based on the pseudo-random properties of certain graphs, known as expanders, is used to obtain new simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling and then regrouping the code coordinates. For any fixed (small) rate, and for sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below Zyablov bound, they are still superior to previously-known explicit constructions in the zero-rate neighborhood.

The paper: Postscript, gzipped Postscript.

Related On-Line Papers:

J. Naor and M. Naor, Small-Bias Probability Spaces: Efficient Constructions and Applications, SIAM J. Comput. 22(4): 838-856 (1993). Abstract , Postscript, gzipped Postscript.
Moni Naor, Constructing Ramsey graphs from small probability spaces, Postscript , gzipped Postscript
Noga Alon and Moni Naor, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, vol 16, 1996, pp. 434-449. Abstract , Postscript , gzipped Postscript

Back to On-Line Publications

Back Home