Some Connections Between the (Weak) Regularity Lemma, Complexity Theory and Additive Combinatorics

SHORT TALKS BY POSTDOCTORAL MEMBERS
Topic:	Some Connections Between the (Weak) Regularity Lemma, Complexity Theory and Additive Combinatorics
Speaker:	Madhur Tulsiani
Affiliation:	Member, School of Mathematics
Date:	Friday, October 2
Time/Room:	2:00pm - 3:00pm/S-101

---

I will discuss the relation between:

(a) the Weak Regularity Lemma of Frieze and Kannan, a result in graph theory,

(b) the "Dense Model Theorem" of Green, Tao and Ziegler, a result in additive combinatorics, that helps transfer results about dense sets of integers to results about the primes, and

(c) the Impagliazzo Hard-Core Set lemma, a result from computational complexity theory.

I will state a general result from which all three follow easily. Also, the proof techniques for each of the above results can be used to prove the general result. If time permits, I will give the sketch of a proof using the technique of ``boosting" from machine learning, which gives the best quantitative parameters.

Based on joint work with Omer Reingold, Luca Trevisan and Salil Vadhan.