Previous Conferences & Workshops

Oct
17
2005

Computer Science/Discrete Mathematics Seminar I

Embeddings of Earthmover Metrics
10:30am|S-101

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

Oct
14
2005

Arithmetic Homogeneous Spaces

Equidistribution and Arithmetic on Homogeneous Spaces
11:00am|S-101

I will discuss the following theme: starting with an a priori Diophantine result (typical flavour: integer solutions to such-and-such equation are well-spaced) and turning it into an equidistribution-type statement on a homogeneous space. This (in...

Oct
11
2005

Lie Groups, Representations and Discrete Mathematics

From Ramanujan Graphs to Ramanujan Complexes
Alex Lubotzky
2:00pm|S-101

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

Oct
10
2005

Computer Science/Discrete Mathematics Seminar I

Randomness Extractors for a Constant Number Independent Sources of Polynomial Min-Entropy
11:15am|S-101

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