2007-2008 seminars

For a probability distribution X over a finite set, let D(X) denote the L_2-distance of X from the uniform distribution. Let X, Y be probability distributions over the finite group G and let Z be their G-convolution. Inspired by recent work of...

An extension of Szemeredi's Regularity Lemma for hypergraphs, was proved in 2005 by Gowers and independently by Rodl, Schacht, Skokan, and Nagle. More recently, Tao gave another proof for the lemma. A special case, the Removal Lemma is an important...

Valiant's theory of holographic algorithms is a new design method to produce polynomial time algorithms. Information is represented in a superposition of linear vectors in a holographic mix. This mixture creates the possibility for exponential sized...

Let Q(n,p) denote the adjacency matrix of the Erdos-Renyi graph G(n,p), that is to say a symmetric matrix whose entries above the main diagonal are independently set to 1 with probability p and 0 with probability 1-p. We will examine the behavior of...

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of...

The notion of a ``market'' has undergone a paradigm shift with the Internet -- totally new and highly successful markets have been defined and launched by companies such as Google, Yahoo!, Amazon, MSN and Ebay. These markets are computationally...

Recent work of Alon-Shapira and Rodl-Schacht has demonstrated that every hereditary graph and hypergraph property is testable with one-sided error. This result appears definitive, but there are some subtleties to it that I will present here. For...

Let ||.|| be any norm on R^d. We consider the question of estimating the minimum over all possible sign sequences e_i=+/-1 of ||e_1 x_1 + e_2 x_2 + ... + e_n x_n||, where the x_i are independent Gaussian vectors on R^d (here d is viewed as fixed and...

A theorem of Green, Tao and Ziegler can be stated (roughly) as follows: if R is a pseudorandom set, and X is a dense subset of R, then there is a "model" Y for X such that Y is a dense set and X and Y are indistinguishable. (The precise statement...

In 1977 Szemeredi proved that any subset of the integers of positive density contains arbitrarily long arithmetic progression. A couple of years later Furstenberg gave an ergodic theoretic proof for Szemeredi's theorem. At around the same time...