I will discuss the Green-Tao proof for existence of arbitrarily long arithmetic progressions in the primes. The focus will primarily be on the parts of the proof which are related to notions in complexity theory. In particular, I will try to describe in detail how the proof can be seen as applying Szemeredi's theorem to primes, by arguing that they are indistinguishable from dense subsets of integers, for a suitable family of distinguishers.
I will first give an overview of several constructions of graph sparsifiers and their properties. I will then present a method of sparsifying a subgraph W of a graph G with optimal number of edges and talk about the implications of subgraph sparsification in constructing nearly-optimal ultrasparsifiers and optimizing the algebraic connectivity of a graph by adding few edges.
The talk is based on joint work with Makarychev,Saberi,Teng.
I will survey some constructions of expander graphs using variants of Kazhdan property T . First, I describe an approach to property T using bounded generation and then I will describe a recent method based on the geometric properties of configurations of subspaces in a finite dimensional Euclidean space.