2020-21 Seminars

In this talk I will present a joint work with Arie Levit and Yair Minsky on flexible stability of surface groups. The proof will be geometric in nature and will rely on an analysis of branched covers of hyperbolic surfaces. Along the way we will see...

Let X and Y be normed spaces. In functional analysis, a ``theorem on factorization through L2'' refers to the following type of statement: 

Every bounded linear operator A mapping X to Y (i.e. sup_x ||A(x)||_Y/||x||_X infinity), can be written as...

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new...

A sofic approximation to a countable discrete group is a sequence of finite models for the group that generalizes the concept of a Folner sequence witnessing amenability of a group and the concept of a sequence of quotients witnessing residual...

Miller computed the character table of $S_n$ for some fairly large n's and noticed that almost all of the entries were even. Based on this, he conjectured that the proportion of even entries in the character table of $S_n$ tends to $1$ as $n\to...

Suppose we have a cancellative binary associative operation * on a finite set X. We say that it is delta-associative if the proportion of triples x, y, z such that x*(y*z) = (x*y)*z is at least delta.

Gowers and Long studied somewhat associative...

A countable group $G$ is called sofic if it admits a sofic approximation: a sequence of asymptotically free almost actions on finite sets. Given a sofic group $G$, it is a natural problem to try to classify all its sofic approximations and, more...

We prove new lower bounds on the well known Gap-Hamming problem in communication complexity. Our main technical result is an anti-concentration bound for the inner product of two independent random vectors. We show that if A, B are arbitrary subsets...

We show that if $G=\langle S | E\rangle$ is a discrete group with Property (T) then $E$, as a system of equations over $S$, is not stable (under a mild condition). That is, $E$ has approximate solutions in symmetric groups $Sym(n)$, $n \geq 1$, that...