| Title: | Error-Correcting Codes: Algorithms and Applications (Part II) |
| Date: |
January 9, 2007 (Tuesday)
|
| Time: |
2:30 p.m. - 4:00 p.m.
|
| Venue: |
Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong, Shatin, N.T. |
| Speaker: |
Professor Luca Trevisan
Department of Computer Science University of California, Berkeley USA |
Error-correcting codes and related combinatorial constructs play a fundamental role in the reliable storage and communication of digital data. Perhaps surprisingly, they have also been central to several recent (and old) results in theoretical computer science, in applications that are quite unrelated to reliable storage and transmission, such as secret-sharing, hashing, private information retrieval, average-case complexity and probabilistically checkable proofs.
This course will give a brief overview of the theory, constructions, algorithms, and applications of error-correcting codes.
We will begin with basic definitions and the constructions of Reed- Solomon, Reed-Muller, and low-weight parity-check codes, then see unique-decoding and list-decoding algorithms. As time allows, we will sketch some of the applications in theoretical computer science.
BIOGRAPHY:
Luca Trevisan is an associate professor of computer science at U.C. Berkeley. Luca received his Laurea (BSc) degree in 1993 and his Dottorato (PhD) in 1997, both from the University of Rome La Sapienza. Before coming to Berkeley in 2000, Luca was a post-doc at MIT and at DIMACS, and an assistant professor at Columbia University.
Luca's research is in theoretical computer science, and most of his work has been in two areas: (i) the relation between pseudorandomness, derandomization, average-case complexity, coding theory, and the explicit construction of expander-like graphs; and (ii) the theory of probabilistically checkable proofs and its relation to the approximability of combinatorial optimization problems.
Luca received the STOC'97 student paper award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He lectured in the 2000 IAS/PCMI Summer School and he was an invited speaker at the 2006 International Congress of Mathematicians in Madrid.
Enquiries: Miss Temmy So at tel 2609 8444
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar