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

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

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