School of Mathematics

An Algorithmic Proof of Forster's Lower Bound

Moritz Hardt
Princeton University
December 15, 2009

We give an algorithmic proof of Forster's Theorem, a fundamental result in communication complexity. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors. We point out an efficient algorithm to compute the radial isotropic position of a given set of vectors when it exists.

Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems

Russell Impagliazzo
Institute for Advanced Study
December 8, 2009

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan, and independently, Gowers, give a quantitatively improved characterization of when such dense models exist. An equivalent formulation was obtained earlier by Barak, Shaltiel and Wigderson.

Arithmetic Progressions in Primes

Madhur Tulsiani
Institute for Advanced Study
November 24, 2009

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.

Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders

Alexandra Kolla
Institute for Advanced Study
November 10, 2009

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.

Constructions of Expanders Using Group Theory

Martin Kassabov
Cornell University; von Neumann Fellow, School of Mathematics
November 3, 2009

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.

Hardness of Projection Games

Dana Moshkovitz
Institute for Advanced Study
October 20, 2009

The PCP Theorem shows that any mathematical proof can be efficiently converted into a form that can be checked probabilistically by making only *two* queries to the proof, and performing a "projection test" on the answers. This means that the answer to the first query determines at most one satisfying answer to the second query.
If the proof is correct, the checking algorithm always accepts. On the other, the probability that the checking algorithm accepts a proof for an invalid statement (this is the "error" of the check), is small.