additive combinatorics and computational complexity

This work is supported by NSF under grant CCF-0729137.

slides

The Beijing lecture on additive combinatorics and computer science, October 2008
- Aimed at computer scientists. Gives an overview of the problems studied in additive combinatorics, and of the applications of the techniques in computer science.
The MSRI lecture on a boosting proof of the weak regularity lemma, November 2008
- Aimed at mathematicians. Discusses the connection between the weak regularity lemma of Frieze and Kannan, the dense model theorem of Green, Tao and Ziegler, and the hard-core set lemma of Impagliazzo.
The Princeton lecture on pseudorandomness in computer science and additive combinatorics, August 2009 [video]
- Aimed at computer scientists. Discusses the relation between analytic notions such as the Gowers norm and the computer science notions of pseudorandomness and indistinguishability.
The IPAM lecture on pseudorandomness in computer science and additive combinatorics, December 2009
- Similar content but aimed at mathematicians, and more technical.

Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan
Dense Subsets of Pseudorandom Sets
Proc. of the 49th IEEE FOCS, pp. 76-85, 2008
James Cook, Omid Etesami, Rachel Miller and Luca Trevisan
Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms
Proc. of 6th TCC, pp. 521-538, 2009
Anindya De and Luca Trevisan
Extractors Using Hardness Amplification.
Proc. of APPROX-RANDOM, pp. 462-475, 2009
Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil Vadhan
Pseudorandom Bit Generators That Fool Modular Sums
Proc. of APPROX-RANDOM, pp. 615-630, 2009
Luca Trevisan
Max Cut and the Smallest Eigenvalue
Proc. of the 41st ACM STOC, pp. 263-272, 2009
Luca Trevisan, Madhur Tulsiani and Salil Vadhan
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution
Proc. of the 24th IEEE Computational Complexity Conference, pp. 126-136, 2009

A Berkeley graduate course on additive combinatorics and computer science is tentatively planned for Spring 2010