[Turkmath:6666] Sabanci University Math Seminar--V. Guruswami

[Cem Güneri]

Degerli Liste Uyeleri,

Asagidaki konusma duyurusunu bilginize sunmak istiyorum.

Saygilarimla,

Cem Guneri

------------------------------------------------------------------------------------


Dear Colleauges,

Professor *Venkatesan Guruswami *from Carnegie Mellon University will 
give a lecture on

*List error-correction algorithms and applications: A survey *

Time:  Monday, November 23, 13.40 - 14.40

Room:  Sabancı University, FENS 2019

Prof. Guruswami's visit is partly supported by TÜBİTAK.


*Abstract: *

The construction of error-correcting codes that achieve the best 
possible trade-off between information rate and the amount of errors 
that can be corrected has been a long sought-after goal. In this talk, I 
will survey some of our work on list decoding, culminating in the 
construction of codes with the optimal rate for any desired 
error-correction radius. I will describe these codes (called folded 
Reed-Solomon codes), and give a peek into the algebraic ideas underlying 
their error-correction. The new algorithms correct a factor of two more 
errors compared to the conventional algorithms currently used in every 
CD player and desktop PC, as well as many other applications.

List decodable codes have also found surprising applications extraneous 
to coding theory, in algorithms, complexity theory, and cryptography. I 
will briefly mention some of these, including a recent construction of 
unbalanced bipartite graphs with near-optimal expansion properties.

----------------------------------------------------------------------

*Bio: *

Venkatesan Guruswami received his Bachelor's degree from the Indian 
Institute of Technology at Madras in 1997 and his Ph.D. from the 
Massachusetts Institute of Technology in 2001. He is currently an
Associate Professor in the Computer Science Department at Carnegie 
Mellon University. From 2002-09, he was a faculty member in the 
Department of Computer Science and Engineering at the University of 
Washington. Dr. Guruswami was a Miller Research Fellow at the University 
of California, Berkeley during 2001-02, and was a member in the School 
of Mathematics, Institute for Advanced Study during
2007-08.

Dr. Guruswami's research interests span a broad array of topics 
including the theory of error-correcting codes, approximation algorithms 
and non-approximability results for NP-hard optimization problems, 
explicit combinatorial constructions and pseudorandomness, 
probabilistically checkable proofs, computational complexity theory, and 
algebraic algorithms.

Dr. Guruswami is a recipient of the Computational Complexity Conference 
best paper award (2007), David and Lucile Packard Foundation Fellowship 
(2005), Alfred P. Sloan Foundation Fellowship
(2005), NSF CAREER award (2004), ACM's Doctoral Dissertation Award 
(2002), and the IEEE Information Theory Society Paper Award (2000).

Dr. Guruswami will be an invited speaker at the International Congress 
of Mathematicians in Hyderabad, 2010