Guest column: error-correcting codes and expander graphs

ABSTRACT

The central algorithmic problem in coding theory is the construction of explicit error-correcting codes with good parameters together with fast algorithms for encoding a message and decoding a noisy received word into the correct message. Over the last decade, significant new developments have taken place on this problem using graph-based/combinatorial constructions that exploit the power of <i>expander graphs</i>. The role of expander graphs in theoretical computer science is by now certainly well-appreciated. Here, we will survey some of the highlights of the use of expanders in constructions of error-correcting codes.

REFERENCES

• 1: N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38:509--516, 1992.
• 2: N. Alon , J. Edmonds , M. Luby, Linear time erasure codes with nearly optimal recovery, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.512, October 23-25, 1995
• 3: N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures and Algorithms, 5:271--284, 1994.
• 4: N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons, Inc., 1992.
• 5: A. Barg and G. Zémor. Error exponents of expander codes. IEEE Transactions on Information Theory, 48(6):1725--1729, June 2002.
• 6: A. Barg and G. Zémor. Concatenated codes: serial and parallel. Manuscript, 2003.
• 7: Alexander Barg , Gilles Zémor, Error Exponents of Expander Codes under Linear-Complexity Decoding, SIAM Journal on Discrete Mathematics, v.17 n.3, p.426-445, 2004 [doi>10.1137/S0895480102403799]
• 8: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 9: J. Feldman and C. Stein. LP decoding achieves capacity. Manuscript, 2004.
• 10: G. D. Forney. Concatenated Codes. MIT Press, Cambridge, MA, 1966.
• 11: R. G. Gallager. Low-density parity-check codes. MIT Press, Cambridge, MA, 1963.
• 12: Venkatesan Guruswami, Better extractors for better codes?, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007422]
• 13: V. Guruswami and P. Indyk. Linear time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory. To appear.
• 14: Venkatesan Guruswami , Piotr Indyk, Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510023]
• 15: Venkatesan Guruswami , Piotr Indyk, Linear time encodable and list decodable codes, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780562]
• 16: V. Guruswami and P. Indyk. Linear-time list decoding in error-free settings. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), July 2004.
• 17: V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and Algebraic-geometric codes. IEEE Transactions on Information Theory, 45(6):1757--1767, 1999.
• 18: A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 19: O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics, 155:157--187, 2002.
• 20: T. Richardson and R. Urbanke. Efficient encoding of low density parity check codes. IEEE Transactions on Information Theory, 47(2):638--656, Feb 2001.
• 21: M. Sipser and D. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710--1722, 1996.
• 22: V. Skachek and R. Roth. Generalized Minimum Distance iterative decoding of expander codes. In Proceedings of IEEE Information Theory Workshop (ITW), pages 245--248. 2003.
• 23: D. Spielman. Constructing error-correcting codes from expander graphs. In Emerging Applications of Number Theory, IMA volumes in mathematics and its applications, volume 109, 1996.
• 24: D. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723--1732, 1996.
• 25: Madhu Sudan, List decoding: algorithms and applications, ACM SIGACT News, v.31 n.1, p.16-27, March 2000 [doi>10.1145/346048.346049]
• 26: M. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533--547, 1981.
• 27: L. Trevisan. Some applications of coding theory in computational complexity. Quaderni di Matematica, 2004. To appear.
• 28: G. Zémor. On expander codes. IEEE Transactions on Information Theory, 47(2):835--837, 2001.