UWTV Program: Linear Time Encodable/Decodable Codes

Search:

Search for information by:

Note: Selected programs are available for streaming download per agreement with the original media source.

Sponsored by:

Linear Time Encodable/Decodable Codes

	Venkatesan Guruswami presents 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. These codes nearly match the "Singleton bound" and thus their rate vs. distance 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.



	* Help?


Series Title:	CSE Colloquia - 2002
Subject(s):	Engineering and Computer Science
Speaker(s):	Venkatasen Guruswami, University of Washington Computer Science & Engineering
Related Link(s):	CSE website
Production Date:	04/04/2002
Runtime:	00:58:25
Rating:	TV-G

Support for UWTV is provided by:

San Jose State @ UW
Watch 9/3 at 8 p.m.
Original Game: 11/16/96

Kansas State @ UW
Watch 9/6 at 7 p.m.
Original Game: 9/28/91

Email us with comments or questions or call 888-616-UWTV