2005-2006 seminars

Earthmover metrics are popular similarity measures in computer vision, and they are also used in the design of approximation algorithms for classification problems. Motivated by the existing nearest neighbor search databases for L_1 metrics, it was...

Ramanujan graphs are grphs with optimal bounds on their eigenvalues. They play an important role in combinatorics and computer science. Their constructions in the late 80's used the work of Deligne and Drinfeld proving the Ramanujan conjecture for...

I will describe in some detail several different applications of expander graphs, which illuminate the need for explicit constructions of expanders with different properties.

We construct an extractor that can extract from a constant number of independent sources of length $n$, each of which have min-entropy $n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our constructions are different from recent extractor...

Szemeredi's regularity lemma asserts, roughly speaking, that any large dense graph can be approximated to any specified accuracy by a much simpler "finite complexity" object; it has had many applications in graph theory, combinatorial number theory...

The product replacement algorithm is a commonly used algorithm to generate a random element in a finite group. While its performance is quite outstanding, its theretical understanding is quite poor. We will present a joint work with Igor Pak (JAMS...

I will talk about a family of graphs which originally arose in cryptography, in studying the difficulty of the discrete logarithm problem on elliptic curves. These graphs can be shown to be expanders, assuming the generalized Riemann hypothesis (GRH...

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the...