In a subsequent work, I extended the construction of expander codes to obtain aymptotically good codes that could be both encoded and decoded in linear time. The construction combines expander codes in a manner analogous to how superconcentrators combine expander graphs. This work appeared in the paper Linear-time encodable and decodable error-correcting codes (IEEE TIT '96)
These two papers formed the bulk of my thesis: Computationally Efficient Error-Correcting Codes and Holographic Proofs (MIT '95)
These works are also described in two survey papers. In Constructing Error-Correcting Codes from Expander Graphs, (IMA '96) we survey the constructions of expander codes and the linear-time encodable and decodable codes. In, The Complexity of Error-Correcting Codes (FCT '97/LNCS #1279), we survey some key developments in the complexity of error-correcting codes and show how to construct linear-time encodable and decodable error-correcting codes that approach the Shannon bound.
Our first work in this direction appeared in the paper Efficient Erasure Correcting Codes (IEEE TIT '01) In which we developed the Tornado Codes, a family of codes that approach the capacity of the erasure channel and that can be encoded and decoded in linear time. These codes have exceedingly fast software implementations and should be useful for compensating for packet loss in internet traffic. While most of the analysis in this paper concerns low-density parity-check codes, which are generally quadratic-time encodable, we use a general technique to combine these to obatain a linear-time encodable code with similar performance.
In, Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation (ISIT '98) we simulated the performance of the codes from the "Efficient Erasure Correcting Codes" paper on the Gaussian channel using belief propagation decoding. We found that the resulting codes performed much better than previous low-density parity-check codes. These experiments demonstrate that irregular LDPC codes can perform much better than regular LDPC codes on the Gaussian channel.
In, Analysis of Low Density Codes and Improved Designs Using Irregular Graphs , (STOC '98) we extend the approach introduced in the erasure code paper to the design and analysis of codes correcting errors. We introduce tools based on linear programming for designing linear time irregular codes with better error-correcting capabilities than possible with regular codes on the binary symmetric channel. We include the results of simulations demonstrating the effectiveness of our codes on systems of reasonable size.
The work in the previous two papers appeared in journal form in Improved Low Density Parity Check Codes Using Irregular Graphs (IEEE TIT '01), which was awarded the 2002 Information Theory Society Paper Award.
In a later paper, Finding good LDPC Codes (Allerton '98), I developed heuristics for finding good irregular LDPC codes, and then used these heuristics to find LDPC codes that were the first to out-perform Turbo codes at very low signal-to-noise ratios.