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 complexity-theoretic 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 "hard-core set lemma"). In complexity-theoretic language, we show that every high min-entropy 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 average-case complexity, including Yao's XOR lemma and O'Donnell's generalization of it, can be easily derived from the existence of such approximators.

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. 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.

Back