Smallbias Probability Spaces: efficient constructions
and Applications
Noga Alon Shuki Bruck Joseph Naor Moni Naor Ronny Roth
Abstract:
A new technique, based on the pseudorandom 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
previouslyknown explicit constructions in the zerorate neighborhood.
The paper: Postscript, gzipped Postscript.
Related OnLine Papers:

J. Naor and M. Naor,
SmallBias Probability Spaces:
Efficient Constructions and Applications, SIAM J. Comput.
22(4): 838856
(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. 434449. Abstract
,
Postscript
,
gzipped
Postscript
Back to OnLine Publications
Back Home