2005-2006 seminars

I will present a recent result by Martin Kassabov, which answers affirmatively a 20 year-old open question: Do the symmetric groups S_n contain bounded-size generating sets U_n such that the Cayley graphs C(S_n,U_n) are (bounded-degree) expander...

Unique games were introduced by Uriel Feige and Laszlo Lovasz. We are given a graph G, a set of labels [k] = {1,...,k}, and permutations pi_{uv} on the set [k] (for all edges (u,v)). Our goal is to find an assignment of labels to variables x(u) (for...

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

I will present a recent result by Martin Kassabov, which answers affirmatively a 20 year-old open question: Do the symmetric groups S_n contain bounded-size generating sets U_n such that the Cayley graphs C(S_n,U_n) are (bounded-degree) expander...

I will discuss the following two results. I will assume no prior knowledge of quantum information or the PCP theorem. 1) The membership of $x$ in $SAT$ (for $x$ of length $n$) can be proved by a logarithmic-size quantum state $\Psi$, together with a...

The van der Waerden conjecture states that the permanent of N by N doubly stochastic matrix A satisfies the inequality Per(A) >= n! / n^n (VDW bound) and was finally proven (independently) by D.I. Falikman and G.P. Egorychev in 1981. It was for more...