| Title: | Pseudorandomness and Combinatorial Constructions |
| Date: |
January 11, 2007 (Thursday)
|
| Time: |
11:00 a.m. - 12:00 noon
|
| 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 |
In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science, probabilistic algorithms are sometimes simpler and more efficient than the best known deterministic algorithms for the same problem.
Despite this evidence for the power of random choices, the computational theory of pseudorandomness shows that, under certain complexity-theoretic assumptions, every probabilistic algorithm has an efficient deterministic simulation and a large class of applications of the the probabilistic method can be converted into explicit constructions.
In this survey talk we describe connections between the conditional "derandomization" results of the computational theory of pseudorandomness and unconditional explicit constructions of certain combinatorial objects such as error-correcting codes and "randomness extractors."
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