%0 Journal Article %1 guruswami04 %A Guruswami, Venkatesan %C New York, NY, USA %D 2004 %I ACM %J SIGACT News %K codes error-correcting-codes %N 3 %P 25--41 %R 10.1145/1027914.1027924 %T Guest Column: Error-correcting Codes and Expander Graphs %V 35 %X 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.

@article{guruswami04, 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.}, acmid = {1027924}, added-at = {2016-07-17T09:22:53.000+0200}, address = {New York, NY, USA}, author = {Guruswami, Venkatesan}, biburl = {https://www.bibsonomy.org/bibtex/27944507c3bd00e281c4a717b06865b26/ytyoun}, doi = {10.1145/1027914.1027924}, interhash = {a59000e5d7024a1b16e3e3ecd2432ec1}, intrahash = {7944507c3bd00e281c4a717b06865b26}, issn = {0163-5700}, issue_date = {September 2004}, journal = {SIGACT News}, keywords = {codes error-correcting-codes}, month = sep, number = 3, numpages = {17}, pages = {25--41}, publisher = {ACM}, timestamp = {2016-08-20T11:00:07.000+0200}, title = {Guest Column: Error-correcting Codes and Expander Graphs}, volume = 35, year = 2004 }