Video Lectures

Can we use computational algorithms to make accurate predictions of physical phenomena? In this talk, intended for non-experts, I will give examples where complicated space-time phenomena can be exquisitely captured with simple computational...

A hardness escalation method applies a simple transformation that increases the complexity of a computational problem. Using multiparty communication complexity we present a generic hardness escalation method that converts any family of...

We construct linear codes of almost-linear length and linear distance that can be locally self-corrected on average from a constant number of queries:

1. Given oracle access to a word $w\in\Sigma^n$ that is at least $\varepsilon$-close to a codeword...

This talk will be a biased survey of recent work on various properties of elements of infinite groups, which can be shown to hold with high probability once the elements are sampled from a large enough subset of the group (examples of groups: linear...

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial...

A permutation pi=(pi_{1},...,pi_{n}) is consecutive 123-avoiding if there is no sequence of the form pi_i pi_{i+1} pi_{i+2}. More generally, for S a collection of permutations on m+1 elements, this definition extends to define consecutive S...

In this expository talk, I will outline a plausible story of how the study of congruences between modular forms of Serre and Swinnerton-Dyer, which was inspired by Ramanujan's celebrated congruences for his tau-function, led to the formulation of...

The famous theorem of Szemerédi says that for any natural number $k$ and any $a > 0$ there exists n such that if $N >= n$ then any subset $A$ of the set $[N] ={1,2,...,N}$ of size $|A| >= a$ $N$ contains an arithmetic progression of length $k$. We...