Sub-Linear Time Error-Correction and Error-Detection

EECS Joint Colloquium Distinguished Lecture Series

Professor Luca Trevisan
EECS Department, U.C. Berkeley

Wednesday, October 18, 2000
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.


Error-correcting codes based on multivariate polynomials admit very efficient (polylogarithmic-time, or even constant-time, if the computational model is sufficiently generous) probabilistic decoding procedures and error-detection procedures.

The efficient decoding procedures can recover (with high probability) a selected bit or block of the original message while given a corrupted encoding; the error-detection procedures can distinguish (with high probability) a valid codeword from a string containing a large fraction of errors.

The existence of such procedures has been known and exploited in complexity theory for a while, and it is relevant to program testing, average-case complexity, probabilistically checkable proofs and private information retrieval.

We are interested in two questions: Is it possible to construct similar procedures for more general classes of codes? Is there a trade-off between the efficiency of the procedures and the information rate of the code?

Partial answers follow from work by several people, including the speaker. More general answers would follow from the resolution of certain conjectures that seem to be of independent interest. In the long run, this line of research could lead, among other things, to a better assessment of the practicality of information-theoretic private information retrieval (a certain class of cryptographic constructions) and to a simpler proof of the hardest part of the PCP Theorem. Hopefully, such codes could be useful to the practice of fault-tolerant information transmission and storage, but this remains to be seen.


Luca Trevisan received his PhD from the University of Rome "La Sapienza" in 1997, and he has later been a post-doc at MIT, a post-doc at DIMACS, and an assistant professor at Columbia University. He is currently an assistant professor at UC Berkeley. Luca received the STOC'97 best student paper award, and is a recipient of the Sloan Research Fellowship and of the NSF Career Award.