2009-2010 Seminars

In this survey lecture (which will continue on Tue Feb 2) I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups. These...

Algorithms spend time on performing arithmetic computations, but often more on moving data, between the levels of a memory hierarchy and between parallel computing entities. Judging by the hardware evolution of the last few decades, the fraction of...

Motivated in part by various sequences of graphs growing under random rules (like internet models), convergent sequences of dense graphs and their limits were introduced by Borgs, Chayes, Lovasz, Sos and Vesztergombi and by Lovasz and Szegedy. In...

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...

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential...

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...

We give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem. The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to...

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...