School of Mathematics

The singularity of symbolic matrices

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
February 9, 2016
The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of rational functions). As it happens, this problem has a dual life; when the underlying variables commute, and when they do not.

Obstructions to minimal fibrations of hyperbolic 3-manifolds

Joel Hass
University of California, Davis; Member, School of Mathematics
February 9, 2016
Through the work of Agol and Wise, we know that all closed hyperbolic 3-manifolds are finitely covered by a surface bundle over the circle. Thus the geometry of these bundles indicates the geometry of general hyperbolic 3-manifolds. But there are still many open problems about these bundles. The main result that I'll discuss shows that there are hyperbolic 3-manifolds that fiber over the circle but that do not admit fibrations by minimal surfaces. These manifolds do not admit fibrations by surfaces that are even approximately minimal.

Bipartite perfect matching is in quasi-NC

Stephen Fenner
University of South Carolina
February 8, 2016
We show that the bipartite perfect matching problem is in $\textrm{quasi-}\textsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the Isolation Lemma of Mulmuley, Vazirani, & Vazirani, used to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

Variance of sums of arithmetic functions over primes in short intervals

Jon Keating
University of Bristol
February 8, 2016
Goldston & Montgomery and Montgomery & Soundararajan have established formulae for the variance of sums of the von Magoldt function over short intervals (i.e. for the variance of the number of primes in these intervals) assuming, respectively, the pair-correlation conjecture and the Hardy-Littlewood conjecture. I will discuss the generalisation of these formulae to other arithmetic functions associated with the Selberg class of L-functions, in the context of both zero statistics and arithmetic correlations.

Profinite rigidity and flexibility for compact 3-manifold groups

Alan Reid
University of Texas, Austin; Member, School of Mathematics
February 2, 2016
This talk will discuss the question: To what extent are the fundamental groups of compact 3-manifolds determined (amongst the fundamental groups of compact 3-manifolds) by their finite quotients. We will discuss work that provides a positive answer for fundamental groups of hyperbolic 1-punctured torus bundles.

Constant-round interactive-proofs for delegating computations

Ron Rothblum
Massachusetts Institute of Technology
February 1, 2016
Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds.

The space of surface shapes, and some applications to biology

Joel Hass
University of California, Davis; Member, School of Mathematics
February 1, 2016
The problem of comparing the shapes of different surfaces turns up in different guises in numerous fields. I will discuss a way to put a metric on the space of smooth Riemannian 2-spheres (i.e. shapes) that allows for comparing their geometric similarity. The metric is based on a distortion energy defined on the space of conformal mappings between a pair of spheres. I'll also discuss a related idea based on hyperbolic orbifold metrics. I will present results of experiments on applying these techniques to biological data.