School of Mathematics

Language edit distance, $(\min,+)$-matrix multiplication & beyond

Barna Saha
University of Massachusetts, Amherst
November 6, 2017

The language edit distance is a significant generalization of two basic problems in computer science: parsing and string edit distance computation. Given any context free grammar, it computes the minimum number of insertions, deletions and substitutions required to convert a given input string into a valid member of the language. In 1972, Aho and Peterson gave a dynamic programming algorithm that solves this problem in time cubic in the string length. Despite its vast number of applications, in forty years there has been no improvement over this running time.

Morse-Bott cohomology from homological perturbation

Zhengyi Zhou
University of California, Berkeley
November 6, 2017
Abstract: In this talk, I will give a new construction of the Morse-Bott cochain complex, where the underlying vector space is generated by the cohomology of the critical manifolds. This new construction has two nice features: (1) It requires the minimum amount of transversality. (2) The choices made in the construction do not depend on the moduli spaces. I will explain its relation to three other constructions in literature, namely Austin-Braam's push-pull construction, Fukaya's push-pull construction and the cascades construction.

Two-bubble dynamics for the equivariant wave maps equation

Jacek Jendrej
University of Chicago
November 2, 2017
I will consider the energy-critical wave maps equation with values in the sphere in the equivariant case, that is for symmetric initial data. It is known that if the initial data has small energy, then the corresponding solution scatters. Moreover, the initial data of any scattering solution has topological degree 0. I try to answer the following question: what are the non-scattering solutions of topological degree 0 and the least possible energy? I will show how to construct such threshold solutions.

On the notion of genus for division algebras and algebraic groups

Andrei Rapinchuk
University of Virginia
November 2, 2017
Let $D$ be a central division algebra of degree $n$ over a field $K$. One defines the genus gen$(D)$ of $D$ as the set of classes $[D']$ in the Brauer group Br$(K)$ where $D'$ is a central division $K$-algebra of degree $n$ having the same isomorphism classes of maximal subfields as $D$. I will review the results on gen$(D)$ obtained in the last several years, in particular the finiteness theorem for gen$(D)$ when $K$ is finitely generated of characteristic not dividing $n$.