Title: Additive CombinatorITCS and Computational Complexity  
Name: Luca Trevisan University of California, Berkeley 

Time:October 14th (Tuesday) 16:4517:30  
Location: Lecture Hall, FIT Building, Tsinghua University  
Host Unit: ITCS, Tsinghua University 
I will outline recent and ongoing work with Omer Reingold, Madhur Tulsiani, and Salil Vadhan on connections between techniques and results in additive combinatorITCS and techniques and results in computational complexity. In this talk I will focus on the application of complexity theoretic techniques to prove results in additive combinatorITCS, and on the complexitytheoretic interpretations of such results.
I will present in some detail a new proof of a generalization of the (weak) Szemeredi regularity lemma, using techniques from "boosting" in learning theory (or, equivalently, from Impagliazzo's proof of the "hardcore set lemma"). In complexitytheoretic language, we show that every high minentropy distribution is indistinguishable from (and thus "modeled" by) an efficiently samplable distribution. We also show that every function is "approximated" by an efficiently computable function such that, roughly speaking, the inputs on which the approximating function makes mistakes are indistinguishable from the inputs on which the approximation is correct. A number of key results in the theory of averagecase complexity, including Yao's XOR lemma and O'Donnell's generalization of it, can be easily derived from the existence of such approximators.
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 postdoc 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, averagecase complexity, coding theory, and the explicit construction of expanderlike graphs; and (ii) the theory of probabilistically checkable proofs and its relation to the approximability of combinatorial optimization problems. For the past two years he has been exploring connections between additive combinatorITCS and theoretical computer science.
Luca received the STOC'97 student paper award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians in Madrid.