School of Mathematics
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 hierarchy collapses. Several optics groups are already working toward doing our experiment.
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 groups over the integers, free groups, hyperbolic groups, mapping class groups, automorphism groups of free groups . . . )
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 $c$, and an index $i\in [n]$ to correct, with high probability over $i$ and over the internal randomness, the local algorithm returns a list of possible corrections that contains $c_i$.
Infinite continuous graphs emerge naturally in the geometric analysis of closed planar sets which cannot be presented as countable union of convex sets. The classification of such graphs leads in turn to properties of large classes of real functions - e.g. the class of Lipschitz continuous functions - and to meta-mathematical properties of sub-ideals of the meager ideal (the sigma-ideal generated by nowhere dense sets over a Polish space) which reduce to finite Ramsey-type relations between random graphs and perfect graphs.
ANALYSIS/MATHEMATICAL PHYSICS SEMINAR
Picard moduli spaces parametrize principally polarized abelian varieties with complex multiplication by the ring of integers in an imaginary-quadratic field. The loci where the abelian varieties split off an elliptic curve in a controlled way are divisors on this moduli space. We study the intersection behaviour of these divisors and prove in the non-degenerate case a relation between their intersection numbers and Fourier coefficients of the derivative at s=0 of a certain incoherent Eisenstein series for the unitary group. This is joint work with Kudla.
GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR
Some automorphic forms, despite the fact they are algebraic, do not have any interpretation as cohomology classes on a Shimura variety: therefore nothing is known at present on their expected arithmetic properties. I shall explain how such forms appear to be related to more general objects (Griffiths-Schmid varieties) and discuss some related rationality questions.
We give an elementary proof of a generalization of Bourgain and Tzafriri's Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.