Departmental Colloquia
Date Time 
Location  Speaker  Title – click for abstract  

02/29 4:00pm 
Bloc 117  Alex Lubotzky Weizmann Institute of Science 
Good locally testable codes
Abstract: An errorcorrecting code is locally testable (LTC) if there is a random tester that reads
only a small number of bits of a given word and decides whether the word is in the code, or at least close to it.
A longstanding problem asks if there exists such a code that also satisfies the golden standards of coding theory:
constant rate and constant distance.
Unlike the classical situation in coding theory, random codes are not LTC, so this problem is a challenge of a new kind. We construct such codes based on what we call (Ramanujan) Left/RightCayley square complexes. These objects seem to be of independent grouptheoretic interest. The codes built on them are 2dimensional versions of the expander codes constructed by Sipser and Spielman (1996). The main result and lecture will be selfcontained. But we hope also to explain how the seminal work of Howard Garland (1972) on the cohomology of quotients of the BruhatTits buildings of padic Lie group has led to this construction (even though it is not used at the end). Based on joint work with I. Dinur, S. Evra, R. Livne, and S. Mozes.  
03/26 4:00pm 
BLOC 117  Persi Diaconis Stanford University 
Adding numbers and shuffling cards
When numbers are added in the usual way, 'carries' occur. Carries make a mess and it's natural to ask 'how do the carries go?' How many carries are typical and, if you just had a carry, is it more or less likely that there is a following carry? Surprisingly, the carries form a Markov chain with an 'amazing' transition matrix (are any matrices amazing?). This same matrix occurs in the analysis of the usual way of riffle shuffling cards. I will explain the 'seven shuffles theorem' and the connection. The same matrix occurs in taking sections of generating functions and in understanding the Veronese embedding. I'll try to explain all of this 'in English'.
 
03/28 4:00pm 
BLOC 117  Persi Diaconis Stanford University 
Hyperplane walks
Picture a collection of hyperplanes in ddimensional Euclidean space. These divided space into chambers (points not on any of the hyperplanes) and faces (points on some hyperplanes). The geometry and combinatorics of such arrangements is a world of its own, with applications in topology,algebraic geometry and every kind of algebra. I'll supplement this by introducing a simple family of random walks on the chambers. These include classical walks (Ehrenfest urn, card shuffling, dynamic storage allocation) but also lots of fresh examples(walks on parking functions!). Strangely, in more or less complete generality, there is a complete theory (all eigenvalues of the associated transition operators and sharp rates of convergence to stationarityknown). Naturally, there are open problems Understanding the stationary distribution of these walks involves the classical problem of sampling from an urn without replacement in various guises and there is a lot we don't know. I'll try to explain all this to a nonspecialist audience.  
04/18 4:00pm 
BLOC 302  Henri Moscovici  Can one hear the zeros of zeta?
Preceding by a halfcentury the wellknown challenge
“Can one hear the shape of a drum?” a similar dare was raised
relative to the Riemann Hypothesis, which in contemporary parlance
goes by the name of “HilbertPolya operator”. Very recently Alain
Connes worked out the heat expansion for such an operator, assuming
its existence. After presenting his results I will discuss the connection
with our joint work on the squareroot of the prolate spheroidal wave
operator, whose spectrum simulates the zeros of Zeta.
