TITLE: Linear Time Encodable/Decodable Codes with Near-Optimal Rate


SPEAKER: Venkatesan Guruswami 
                  (University of California, Berkeley)


ABSTRACT:


We present a simple, explicit construction of error-correcting codes
that have a near-optimal rate vs. error-correction trade-off and are
encodable and decodable in linear time. Formally, we construct, for
every r (0 < r < 1), a family of codes of rate r that can be
encoded in linear time and decoded in linear time from up to a
fraction (1-r-\epsilon)/2 of errors, for arbitrary \epsilon >
0. The codes are defined over a fixed alphabet whose size depends
only on \epsilon. These codes nearly match the ``Singleton bound''
and thus their rate vs. error-correction trade-off is essentially
optimal, and so is their encoding/decoding time (up to constant
factors).  Previously known codes over a constant-sized alphabet that
approached the Singleton bound (eg. certain algebraic-geometric codes)
suffered from complicated constructions and/or high (certainly,
super-linear) encoding/decoding complexity.


Concatenating these codes with a suitable inner code of constant size
yields constructions of linear time encodable/decodable binary codes
that match the so-called ``Zyablov bound'' (the best rate vs. distance
trade-off known for explicit binary codes with reasonable decoding
complexity), for the entire range of error fractions. In contrast,
previously known linear-time binary codes, due to (Spielman, 1996),
could only correct a very small fraction (about 10^{-6}) of errors.


Our approach is to first construct, by adapting techniques from a
recent work of (Zemor, 2001), certain high rate linear-time codes that can
correct a small fraction of errors, and then to increase the
error-resilience using expanders akin to an approach used for erasure
codes by (Alon, Edmonds, Luby, 1995).


Joint work with Piotr Indyk (MIT).