演讲人： Luca Trevisan University of California, Berkeley
时间： 2008-03-24 14:00-2008-03-24 15:00
地点：FIT Building 4-603, Tsinghua University
内容：

A theorem of Green, Tao and Ziegler can be stated (roughly) as follows: if R is a pseudorandom set, and D is a dense subset of R, then there is a "model" set M for D such that M is a dense set and D and M are indistinguishable. (The precise statement refers to "measures" or distributions rather than sets.) The proof is very general, and it applies to notions of pseudorandomness and indistinguishability defined in terms of any family of adversaries. The proof proceeds via iterative partitioning and an energy increment argument, in the spirit of the proof of the weak Szemeredi regularity lemma. The "reduction" involved in the proof has exponential complexity in the distinguishing probability.
        We present a new proof inspired by Nisan's proof of the Impagliazzo hard core set theorem. The reduction in our proof has polynomial complexity in the distinguishing probability and provides a new characterization of the notion of "pseudoentropy" of a distribution.
        Following the connection between this theorem and the Impagliazzo hard core set theorem in the opposite direction, we present a new proof of the Impagliazzo hard core set theorem via iterative partitioning and energy increment. While our reduction has exponential complexity in some parameters, it has certain consequences that do not seem to follow from known proofs.
        This is joint work with Omer Reingold, Madhur Tulsiani and Salil Vadhan.
 

个人简介:

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 related to pseudorandomness, average-case complexity, explicit combinatorial constructions, and approximability of combinatorial optimization problems.
Luca received the STOC 1997 student paper award (now known as the Danny Lewin 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.