2005-2006 seminars

We prove a general result bridging the fields of Secure Protocols and Game Theory. We show that ANY mediated game with incomplete information can be perfectly simulated by the players alone, essentially by means of an extensive-form game in which...

For a discrete group G and a finite subset X of G, let K(G, X) denote the Kazhdan constant of G associated to X. We define the uniform Kazhdan constant of G by K(G) = min { K(G,X) | X is finite and generates G }. Obviously K(G)>0 for any finite...

We give three different analytic interpretations of Szemeredi's famous Regularity Lemma. The first one is a general statement about Hilbert spaces. The second one presents the Regularity Lemma as the compactness of a certain metric space. The third...

A code is said to be locally testable if an algorithm can distinguish between a codeword and a vector being essentially far from the code using a number of queries that is independent of the code's length. The question of characterizing codes that...

The talk will be introductory. We will first explain what Kac-Moody groups are. These groups are defined by generators and relations, but they are better understood via their actions on buildings. The involved class of buildings is interesting since...

Bi-lipschitz embeddings of finite metric spaces into Hilbert space have become an increasingly important tool in discrete mathematics and theoretical computer science. For example, this theory is intimately related to the algorithmic problem of...

Consider an affine building of type $A_n$-tilde, which is a simplicial compex of dimension $n$. For $n=1$, this is a tree, which we will require to be homogeneous. Consider the space of complex valued functions on the vertices of the building, and...