Mathematics

From the dynamics of surface automorphisms to the computational complexity of 3-manifolds

Eric Samperton (UCSB)

Abstract: Every 3-manifold admits a Heegaard splitting, and many 3-manifold invariants admit formulas using Heegaard splittings. These facts are one starting point for a common theme in the study of 3-manifolds: one can relate various topological or geometric properties of 3-manifolds to dynamical systems in 1 or 2 dimensions. We’ll explore this theme in the context of computational complexity. I’ll start with two examples (coloring invariants and the Jones polynomial) that translate dynamical properties of mapping class group actions into complexity-theoretic hardness properties of 3-manifold invariants. I’ll conclude with some brainstorming about future directions. I will introduce all of the necessary complexity theory as we go.

Tame and wild structures with randomness

Minh Chieu Tran (UIUC)

Abstract: We consider structures built up from components interacting in a partially random fashion with one another. Initially, we were lead to the study of such structures in an attempt to answer a question by van den Dries, Hrushovski, and Kowalski on finding applications of number-theoretic character sum results in model theory. Ultimately, we realized that the underlying idea can be used to built a general frame work that allows us to understand many examples and phenomena of the area. (This talk contains results from joint works with Bhardwaj, Kruckman, and Walsberg).

Unlabeled distance geometry problem

Ivan Dokmanic   [email] (Illinois - Electrical and Computer Engineering)

Abstract: The famous distance geometry problem (DGP) asks to reconstruct the geometry of a point set from a subset of interpoint distances. In the unlabeled DGP the goal is the same, alas without knowing which distances belong to which pairs of points. Both problems are of practical importance: the DGP models sensor network localization, clock synchronization, and molecular geometry reconstruction from NMR data, while the unlabeled DGP models room geometry reconstruction from echoes, positioning by multipath, and nanostructure determination by powder diffraction. The unlabeled DGP in 1D is known as the turnpike reconstruction problem, and it was one of the first techniques used to reconstruct genomes. The mathematics of the unlabeled DGP is nowhere near as well-understood as that of the DGP. I will introduce the unlabeled DGP, explain how it arises in various applications, discuss connections with phase retrieval and explain our approach based on empirical measure matching. Along the way I will point out numerous theoretical and algorithmic aspects of the problem that we do not understand but we wish we did.

Polynomial-Time Approximation Scheme for the Genus of Dense Graphs

Yifan Jing (Illinois Math)

Abstract: The graph genus problem is a fundamental problem in topological graph theory and theoretical computer science. In this talk, we provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. The running time of the algorithm is quadratic. Moreover, we extend the algorithm to output an embedding (rotation system), whose genus is arbitrarily close to the minimum genus, and the expected running time is also quadratic. This is joint work with Bojan Mohar.

A geometric model for complex analytic equivariant elliptic cohomology

Arnav Tripathy (Harvard)

Abstract: Elliptic cohomology has always been a natural big brother to ordinary cohomology and K-theory and is often implicated in the trichotomies of integrable systems or geometric representation theory. However, computations with elliptic cohomology are often made difficult by the fact that we do not know geometric representatives for elliptic cohomology classes. I will explain in this talk a step forward, in joint work with D. Berwick-Evans, for the case of equivariant elliptic cohomology over the complex numbers by using geometric constructions inspired by supersymmetric field theory. This talk will need no prior knowledge of either elliptic cohomology or field theories.