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