Colloquia/Fall18

Mathematics Colloquium

All colloquia are on Fridays at 4:00 pm in Van Vleck B239, unless otherwise indicated.

Fall 2013

date	speaker	title	host(s)
Sept 6	Matt Baker (Georgia Institute of Technology)	Riemann-Roch for Graphs and Applications	Ellenberg
Sept 13	Uri Andrews (University of Wisconsin)	A hop, skip, and a jump through the degrees of relative provability
Sept 20	Valerio Toledano Laredo (Northeastern)	Flat connections and quantum groups	Gurevich
Wed, Sept 25, 2:30PM in B139	Ayelet Lindenstrauss (Indiana University)	Taylor Series in Homotopy Theory	Meyer
Wed, Sept 25 (LAA lecture)	Jim Demmel (Berkeley)	Communication-Avoiding Algorithms for Linear Algebra and Beyond	Gurevich
Thurs, Sept 26 (LAA lecture, Joint with Applied Algebra Seminar)	Jim Demmel (Berkeley)	Implementing Communication-Avoiding Algorithms	Gurevich
Sept 27 (LAA lecture)	Jim Demmel (Berkeley)	Communication Lower Bounds and Optimal Algorithms for Programs that Reference Arrays	Gurevich
Oct 4	Frank Sottile (Texas A&M)	Galois groups of Schubert problems	Caldararu
Oct 11	Amie Wilkinson (Chicago)	Robust mechanisms for chaos	WIMAW (Cladek)
Tues, Oct 15, 4PM (Distinguished Lecture)	Alexei Borodin (MIT)	Integrable probability I	Valko
Wed, Oct 16, 2:30PM (Distinguished Lecture)	Alexei Borodin (MIT)	Integrable probability II	Valko
Oct 18	No colloquium due to the distinguished lecture
Oct 25	Paul Garrett (Minnesota)	Boundary-value problems, generalized functions, and zeros of zeta functions	Gurevich
Nov 1	Allison Lewko (Columbia University)	On sets of large doubling, Lambda(4) sets, and error-correcting codes	Stovall
Nov 8	Tim Riley (Cornell)	Hydra groups	Dymarz
Nov 15 and later	Reserved		Street
Mon, Nov 25, 4PM	Lin Lin (Lawrence Berkeley National Lab)	Fast algorithms for electronic structure analysis	Jin
Mon, Dec 2, 4PM	Simon Marshall (Northwestern)		Seeger
Fri, Dec. 6 and Sat Dec. 7	No Seminar	Conference in honor of Dick Askey

Spring 2014

date	speaker	title	host(s)
Jan 24	Mihnea Popa (UIC)		Arinkin
Jan 31	Urbashi Mitra (USC)		Gurevich
Feb 7	David Treumann (Boston College)		Street
Feb 14	Alexander Karp (Columbia Teacher's College)		Kiselev
Feb 21	Michael Shelley (Courant)		Spagnolie
Feb 28
March 7	Steve Zelditch (Northwestern)		Seeger
March 14	Temporarily reserved		Spagnolie
March 21	Spring Break	No Colloquium
March 28	Michael Lacey (GA Tech)	The Two Weight Inequality for the Hilbert Transform	Street
April 4	Richard Schwartz (Brown)		Mari-Beffa
April 11	Risi Kondor (Chicago)		Gurevich
April 18 (Wasow Lecture)	Christopher Sogge (Johns Hopkins)		Seeger
April 25	Charles Doran(University of Alberta)		Song
Monday, April 28 (Distinguished Lecture)	David Eisenbud(Berkeley)	A mystery concerning algebraic plane curves	Maxim
Tuesday, April 29 (Distinguished Lecture)	David Eisenbud(Berkeley)	Matrix factorizations old and new	Maxim
Wednesday, April 30 (Distinguished Lecture)	David Eisenbud(Berkeley)	Easy solution of polynomial equations over finite fields	Maxim
May 2	Lek-Heng Lim (Chicago)		Boston
May 9	Rachel Ward (UT Austin)		WIMAW

Abstracts

Sep 6: Matt Baker (GA Tech)

Riemann-Roch for Graphs and Applications

We will begin by formulating the Riemann-Roch theorem for graphs due to the speaker and Norine. We will then describe some refinements and applications. Refinements include a Riemann-Roch theorem for tropical curves, proved by Gathmann-Kerber and Mikhalkin-Zharkov, and a Riemann-Roch theorem for metrized complexes of curves, proved by Amini and the speaker. Applications include a new proof of the Brill-Noether theorem in algebraic geometry (work of by Cools-Draisma-Payne-Robeva), a "volume-theoretic proof" of Kirchhoff's Matrix-Tree Theorem (work of An, Kuperberg, Shokrieh, and the speaker), and a new Chabauty-Coleman style bound for the number of rational points on an algebraic curve over the rationals (work of Katz and Zureick-Brown).

Sep 13: Uri Andrews (UW-Madison)

A hop, skip, and a jump through the degrees of relative provability

The topic of this talk arises from two directions. On the one hand, Gödel's incompleteness theorem tell us that given any sufficiently strong, consistent, effectively axiomatizable theory T for first-order arithmetic, there is a statement that is true but not provable in T. On the other hand, over the past seventy years, a number of researchers studying witnessing functions for various combinatorial statements have realized the importance of fast-growing functions and the fact that their totality is often not provable over a given sufficiently strong, consistent, effectively axiomatizable theory T for first-order arithmetic (e.g. the Paris-Harrington and the Kirby-Paris theorems).

I will talk about the structure induced by giving the order (for a fixed T) of relative provability for totality of algorithms. That is, for algorithms describing functions f and g, we say f ≤ g if T along with the totality of g suffices to prove the totality of f. It turns out that this structure is rich, and encodes many facets of the nature of provability over sufficiently strong, consistent, effectively axiomatizable theories for first-order arithmetic. (Work joint with Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller.)

Sep 20: Valerio Toledano Laredo (Northeastern)

Flat connections and quantum groups

Quantum groups are natural deformations of the Lie algebra of nxn matrices, and more generally of semisimple Lie algebras. They first arose in the mid eighties in the study of solvable models in statistical mechanics.

I will explain how these algebraic objects can serve as natural receptacles for the (transcendental) monodromy of flat connections arising from representation theory.

These connections exist in rational, trigonometric and elliptic forms, and lead to quantum groups of increasing interest and complexity.

Wed, Sept 25, 2:30PM Ayelet Lindenstrauss (Indiana University)

Taylor Series in Homotopy Theory

I will discuss Goodwillie's calculus of functors on topological spaces. To mimic the set-up in real analysis, topological spaces are considered small if their nontrivial homotopy groups start only in higher dimensions. They can be considered close only in relation to a map between them, but a map allows us to construct the difference between two spaces, and two spaces are close if the difference between them is small. Spaces can be summed (in different ways) by taking twisted products of them. It is straightforward to construct the analogs of constant, linear, and higher degree homogenous functors, and they can be assembled into "polynomials" and "infinite sums". There are notions of differentiability and higher derivatives, of Taylor towers, and of analytic functions.

What might look like a game of analogies is an extremely useful tool because when one looks at functors that map topological spaces not into the category of topological spaces, but into the category of spectra (the stabilized version of the category of spaces, which will be explained), many of them are, in fact, analytic, so they can be constructed from the homogenous functors of different degrees. And we can use appropriate analogs of calculus theorems to understand them better. I will conclude with some recent work of Randy McCarthy and myself, applying Goodwillie's calculus to algebraic K-theory calculations.

Sep 25: Jim Demmel (Berkeley)

Communication Avoiding Algorithms for Linear Algebra and Beyond

Algorithm have two costs: arithmetic and communication, i.e. moving data between levels of a memory hierarchy or processors over a network. Communication costs (measured in time or energy per operation) already greatly exceed arithmetic costs, and the gap is growing over time following technological trends. Thus our goal is to design algorithms that minimize communication. We present algorithms that attain provable lower bounds on communication, and show large speedups compared to their conventional counterparts. These algorithms are for direct and iterative linear algebra, for dense and sparse matrices, as well as direct n-body simulations. Several of these algorithms exhibit perfect strong scaling, in both time and energy: run time (resp. energy) for a fixed problem size drops proportionally to the number of processors p (resp. is independent of p). Finally, we describe extensions to algorithms involving arbitrary loop nests and array accesses, assuming only that array subscripts are affine functions of the loop indices.

Sep 26: Jim Demmel (Berkeley)

Implementing Communication Avoiding Algorithms

Designing algorithms that avoiding communication, attaining lower bounds if possible, is critical for algorithms to minimize runtime and energy on current and future architectures. These new algorithms can have new numerical stability properties, new ways to encode answers, and new data structures, not just depend on loop transformations (we need those too!). We will illustrate with a variety of examples including direct linear algebra (eg new ways to perform pivoting, new deterministic and randomized eigenvalue algorithms), iterative linear algebra (eg new ways to reorganize Krylov subspace methods) and direct n-body algorithms, on architectures ranging from multicore to distributed memory to heterogeneous. The theory describing communication avoiding algorithms can give us a large design space of possible implementations, so we use autotuning to find the fastest one automatically. Finally, on parallel architectures one can frequently not expect to get bitwise identical results from multiple runs, because of dynamic scheduling and floating point nonassociativity; this can be a problem for reasons from debugging to correctness. We discuss some techniques to get reproducible results at modest cost.

Sep 27: Jim Demmel (Berkeley)

Communication Lower Bounds and Optimal Algorithms for Programs that Reference Arrays

Our goal is to minimize communication, i.e. moving data, since it increasingly dominates the cost of arithmetic in algorithms. Motivated by this, attainable communication lower bounds have been established by many authors for a variety of algorithms including matrix computations.

The lower bound approach used initially by Irony, Tiskin and Toledo for O(n^3) matrix multiplication, and later by Ballard et al for many other linear algebra algorithms, depends on a geometric result by Loomis and Whitney: this result bounds the volume of a 3D set (representing multiply-adds done in the inner loop of the algorithm) using the product of the areas of certain 2D projections of this set (representing the matrix entries available locally, i.e., without communication).

Using a recent generalization of Loomis' and Whitney's result, we generalize this lower bound approach to a much larger class of algorithms, that may have arbitrary numbers of loops and arrays with arbitrary dimensions, as long as the index expressions are affine combinations of loop variables. In other words, the algorithm can do arbitrary operations on any number of variables like A(i1,i2,i2-2*i1,3-4*i3+7*i_4,…). Moreover, the result applies to recursive programs, irregular iteration spaces, sparse matrices, and other data structures as long as the computation can be logically mapped to loops and indexed data structure accesses.

We also discuss when optimal algorithms exist that attain the lower bounds; this leads to new asymptotically faster algorithms for several problems.

October 4: Frank Sottile (Texas A&M)

Galois groups of Schubert problems

Work of Jordan from 1870 showed how Galois theory can be applied to enumerative geometry. Hermite earlier showed the equivalence of Galois groups with geometric monodromy groups, and in 1979 Harris used this to study Galois groups of many enumerative problems. Vakil gave a geometric-combinatorial criterion that implies a Galois group contains the alternating group. With Brooks and Martin del Campo, we used Vakil's criterion to show that all Schubert problems involving lines have at least alternating Galois group. White and I have given a new proof of this based on 2-transitivity.

My talk will describe this background and sketch a current project to systematically determine Galois groups of all Schubert problems of moderate size on all small classical flag manifolds, investigating at least several million problems. This will use supercomputers employing several overlapping methods, including combinatorial criteria, symbolic computation, and numerical homotopy continuation, and require the development of new algorithms and software.

October 11: Amie Wilkinson (Chicago)

Robust mechanisms for chaos

What are the underlying mechanisms for robustly chaotic behavior in smooth dynamics?

In addressing this question, I'll focus on the study of diffeomorphisms of a compact manifold, where "chaotic" means "mixing" and and "robustly" means "stable under smooth perturbations." I'll describe recent advances in constructing and using tools called "blenders" to produce stably chaotic behavior with arbitrarily little effort.

October 15 (Tue) and October 16 (Wed): Alexei Borodin (MIT)

Integrable probability I and II

The goal of the talks is to describe the emerging field of integrable probability, whose goal is to identify and analyze exactly solvable probabilistic models. The models and results are often easy to describe, yet difficult to find, and they carry essential information about broad universality classes of stochastic processes.

October 25: Paul Garrett (Minnesota)

Boundary-value problems, generalized functions, and zeros of zeta functions

Modern analysis (Beppo Levi, Sobolev, Friedrichs, Schwartz) illuminates work of D. Hejhal and Y. Colin de Verdiere from 30 years ago, clarifying, as in P. Cartier's letter to A. Weil, "how the Riemann Hypothesis was not proven". (Joint with E. Bombieri.)

November 1: Allison Lewko (Columbia University)

On sets of large doubling, Lambda(4) sets, and error-correcting codes

We investigate the structure of finite sets A of integers such that A+A is large, presenting a counterexample to natural conjectures in the pursuit of an "anti-Freiman" theory in additive combinatorics. We will begin with a brief history of the problem and its connection to the study of Lambda(4) sets in harmonic analysis, and then we will discuss our counterexample and its construction from error-correcting codes. We will conclude by describing some related open problems. This is joint work with Mark Lewko.

November 8: Tim Riley (Cornell)

Hydra groups

A few years ago Will Dison and I constructed a family of finitely generated groups whose workings include a string-rewriting phenomenon of extraordinary duration which is reminiscent of Hercules' battle with the hydra. I will describe this and the investigations it spurred in hyperbolic geometry, combinatorial group theory, and a problem of how to calculate efficiently with hugely compressed representations of integers.

Monday, Nov 25: Lin Lin (Lawrence Berkeley National Lab)

Fast algorithms for electronic structure analysis

Kohn-Sham density functional theory (KSDFT) is the most widely used electronic structure theory for molecules and condensed matter systems. For a system with N electrons, the standard method for solving KSDFT requires solving N eigenvectors for an O(N) * O(N) Kohn-Sham Hamiltonian matrix. The computational cost for such procedure is expensive and scales as O(N^3). We have developed pole expansion plus selected inversion (PEXSI) method, in which KSDFT is solved by evaluating the selected elements of the inverse of a series of sparse symmetric matrices, and the overall algorithm scales at most O(N^2) for all materials including insulators, semiconductors and metals. The PEXSI method can be used with orthogonal or nonorthogonal basis set, and the physical quantities including electron density, energy, atomic force, density of states, and local density of states are calculated accurately without using the eigenvalues and eigenvectors. The recently developed massively parallel PEXSI method has been implemented in SIESTA, one of the most popular electronic structure software using atomic orbital basis set. The resulting method can allow accurate treatment of electronic structure in a unprecedented scale. We demonstrate the application of the method for solving graphene-like structures with more than 20,000 atoms, and the method can be efficiently parallelized 10,000 - 100,000 processors on Department of Energy (DOE) high performance machines.

March 28: Michael Lacey (GA Tech)

The Two Weight Inequality for the Hilbert Transform

The individual two weight inequality for the Hilbert transform asks for a real variable characterization of those pairs of weights (u,v) for which the Hilbert transform H maps L^2(u) to L^2(v). This question arises naturally in different settings, most famously in work of Sarason. Answering in the positive a deep conjecture of Nazarov-Treil-Volberg, the mapping property of the Hilbert transform is characterized by a triple of conditions, the first being a two-weight Poisson A2 on the pair of weights, with a pair of so-called testing inequalities, uniform over all intervals. This is the first result of this type for a singular integral operator. (Joint work with Sawyer, C.-Y. Shen and Uriate-Tuero)

Past talks

Last year's schedule: Colloquia 2012-2013