School of Mathematics

A PSPACE construction of a hitting set for the closure of small algebraic circuits

Amir Shpilka
Tel Aviv University
December 12, 2017

We study the complexity of constructing a hitting set for the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given nsr in unary outputs a set of inputs from of size poly(nsr), with poly(nsr) bit complexity, that hits all $n$-variate polynomials of degree $r$ that are the limit of size $s$ algebraic circuits.

Recent developments in knot contact homology

Lenny Ng
Duke University
December 11, 2017
Knot contact homology is a knot invariant derived from counting holomorphic curves with boundary on the Legendrian conormal to a knot. I will discuss some new developments around the subject, including an enhancement that completely determines the knot (joint work with Tobias Ekholm and Vivek Shende) and recent progress in the circle of ideas connecting knot contact homology, recurrence relations for colored HOMFLY polynomials, and topological strings (joint work in progress with Tobias Ekholm).

Recent advances in high dimensional robust statistics

Daniel Kane
University of California, San Diego
December 11, 2017
It is classically understood how to learn the parameters of a Gaussian even in high dimensions from independent samples. However, estimators like the sample mean are very fragile to noise. In particular, a single corrupted sample can arbitrarily distort the sample mean. More generally we would like to be able to estimate the parameters of a distribution even if a small fraction of the samples are corrupted, potentially adversarially.

Integral points and curves on moduli of local systems

Junho Peter Whang
Princeton University
December 8, 2017
The classical affine cubic surface of Markoff has a well-known interpretation as a moduli space for local systems on the once-punctured torus. We show that the analogous moduli spaces for general topological surfaces form a rich family of log Calabi-Yau varieties, where a structure theorem for their integral points can be established using mapping class group descent. Related analysis also yields new results on the arithmetic of algebraic curves in these moduli spaces, including finiteness of imaginary quadratic integral points for non-special curves.