## Thursday, July 03, 2008

### Additive Combinatorics and Computer Science

Mini-Course: August 23-24 at Princeton University

• Introduction and overview
• Szemerédi regularity lemma and Szemerédi's theorem for k = 3
• The sum-product theorem and its applications
• Proof of the sum-product theorem
• Proof of the regularity lemma
• Szemerédi's theorem for k = 3: Roth's proof
• Gowers uniformity norms and sketch of Gowers' proof of Szemerédi's theorem
• Applications: Direct Product Theorems
• Applications: PCPs and pseudorandomness

Also:
Luca Trevisan's Blog: in theory

Joseph, Chuang-Chieh Lin said...

The lecture is very clear (according to what I have read so far).

I think Part 2 and 5 can be read first. They explain the regularity lemma clearly (at least to me).

Joseph, Chuang-Chieh Lin said...

A good comment:

"... a bipartite graph is ε-regular if its edges are dispersed like a random graph's..."

Actually, if the edges of a bipartite graph are NOT spread "uniformly", they will disobey the regularity (you could just choose the small degree vertices to be a troublesome subset), and also disobey, somehow, the "randomness" in some sense.

Joseph, Chuang-Chieh Lin said...

I made slides to introduce the regularity lemma and one of its simple applications (testing triangle-freeness).

I asked Peter to arrange a date for me to give a talk. The date might be tomorrow (July 8, 2008).

My wife, Maggie, told me that I worked too hard recently. But I think I am really interested in doing research for the moment.

BarrosH said...

Luca 的腔調我實在聽不懂....Orz 我放棄了XD