2005-2006 seminars

The Grothendieck constant of a graph is an invariant whose study, which is motivated by algorithmic applications, leads to several extensions of a classical inequality of Grothendieck. This invariant was introduced in a joint paper with Makarychev...

We give asymptotically precise estimates for the expected time taken for a random walk to visit all vertices of a graph, viz. the cover time. We do this for several models of random graphs viz. $G_{n,p}$ when $p$ is above the connectivity threshold...

We prove that if a Cartesian product of alternating groups is topologically finitely generated, then it is the profinite completion of a finitely Generated residually finite group. The same holds for Cartesian products of other simple groups under...

This talk is about joint work with A. Lubotzky. Let $F_n$ be the free group on $n\ge 2$ elements and $\A(F_n)$ its group of automorphisms. We have contructed new linear representations of $\A(F_n)$ arising through the action of finite index...

We will discuss the following very recent result: Theorem. Let R be any finitely generated associative (not necessarily commutative) ring, with 1. Then for any n > stable range rank of the ring R, the group EL_n(R) has Kazhdan's property (T). The...

A finitely generated group is called a Golod-Shafarevich group if it has a presentation with the following property: There exists a prime number p and a real number 0

A RED/BLUE coloring of a graph is called $C$-relaxed if the RED vertices form an independent set, while the BLUE vertices induce connected components of order at most $C$. We show that there exists a smallest integer $C$ such that every cubic graph...

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an...

In 1969 Strassen discovered the surprising fact that it is possible to multiply two 2x2 matrices by using only 7 multiplications. This leads to an algorithm which multiplies two nxn matrices with n^(2.81+o(1)) field operations. Coppersmith and...

One-way functions (i.e., polynomial-time computable functions that are hard to invert on the average case) are the cornerstone of modern cryptography. The hardness condition on the task of inverting a one-way function is an *average-case* complexity...