Thursday, July 03, 2008

Additive Combinatorics and Computer Science

從 BarrosH 那邊得到了以下資訊,感謝他的提供。

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

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