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.
papers
- Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan
Dense Subsets of Pseudorandom Sets
Proc. of the 49th IEEE FOCS, 2008
- Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan
New Proofs of the Green-Tao-Ziegler
Dense Model Theorem: An Exposition
Expository note, June 2008
- Luca Trevisan, Madhur Tulsiani and Salil Vadhan
Regularity, Boosting,
and Efficiently Simulating Every High-Entropy Distribution
ECCC TR-08-103, November 2008
other writings
Expository notes on additive
combinatorics and on pseudorandomness,
expanders and
regularity lemmas.
teaching
The Princeton Minicourse
on additive combinatorics and computer science, August 2007
A Berkeley graduate course on additive combinatorics and computer science is tentatively
planned for Spring 2010