Eigenvalue bounds on sums of random matrices

Adam Marcus
Princeton University; Member, School of Mathematics
November 14, 2016
For certain applications of linear algebra, it is useful to understand the distribution of the largest eigenvalue of a finite sum of discrete random matrices. One of the useful tools in this area is the "Matrix Chernoff" bound which gives tight concentration around the largest eigenvalue of the expectation. In some situations, one can get better bounds by showing that the sum behaves (in some rough way) like one would expect from Gaussian random matrices.

Non-malleable extractors for constant depth circuits, and affine functions

Eshan Chattopadhyay
Member, School of Mathematics
November 15, 2016
Seeded and seedless non-malleable extractors are non-trivial generalizations of the more commonly studied seeded and seedless extractors. The original motivation for constructing such non-malleable extractors are from applications to cryptography (privacy amplification and tamper-resilient cryptography). Interestingly, explicitly constructing non-malleable extractors have led to many new connections and progress in pseudoranomness as well.

The gauged symplectic sigma-model

Constantin Teleman
University of California, Berkeley and Oxford University
November 15, 2016
I will recall the construction of the space of states in a gauged topological A-model. Conjecturally, this gives the quantum cohomology of Fano symplectic quotients: in the toric case, this is Batyrev’s presentation of quantum cohomology of toric varieties. Time permitting, I will discuss the role of “Coulomb branches” in gauge theory in relation to equivariant quantum and symplectic cohomology.

Nonabelian Cohen-Lenstra heuristics and function field theorems

Melanie Wood
University of Wisconsin–Madison
November 17, 2016
The Cohen-Lenstra Heuristics conjecturally give the distribution of class groups of imaginary quadratic fields. Since, by class field theory, the class group is the Galois group of the maximal unramified abelian extension, we can consider the Galois group of the maximal unramified extension as a non-abelian generalization of the class group. We will explain non-abelian analogs of the Cohen-Lenstra heuristics due to Boston, Bush, and Hajir and work, some joint with Boston, proving cases of the non-abelian conjectures in the function field analog.

"Rogue Philologists: the Puzzling Case of Huang Kan’s Commentary in Tokugawa Japan (1603-1867) and Qing China (1644-1911)”

Benjamin Elman
Princeton University
November 18, 2016
S.T. Lee Lecture: Philologists as Rogues?
Benjamin Elman, Gordon Wu ’58 Professor of Chinese Studies at Princeton University and former Mellon Visiting Professor (1999-2001) in the School of Historical Studies at the Institute, will deliver a public lecture, “Philologists as Rogues? The Life of a Confucian Classic Recovered in Early Modern Japan and Its Transmission Back to Imperial China,” on Friday, November 18, at 4:30 p.m. in West Lecture hall on the Institute campus.

On the effect of randomness on planted 3-coloring models

Uri Feige
Weizmann Institute of Science
November 21, 2016
The random planted 3-coloring model generates a 3-colorable graph $G$ by first generating a random host graph $H$ of average degree $d$, and then planting in it a random 3-coloring (by giving each vertex a random color and dropping the monochromatic edges). For a sufficiently large constant $c$, Alon and Kahale [SICOMP 1997] presented a spectral algorithm that finds (with high probability) the planted 3-coloring of such graphs whenever $d > c\log n$.

Modular forms with small Fourier coefficients

Florian Sprung
Princeton University; Visitor, School of Mathematics
November 21, 2016
Computing the class number is a hard question. In 1956, Iwasawa announced a surprising formula for an infinite family of class numbers, starting an entire theory that lies behind this phenomenon. We will not focus too much on this theory (Iwasawa theory), but rather describe some analogous formulas for modular forms. Their origins have not been explained yet, especially when the $p$-th Fourier coefficient is small.

Theory of accelerated methods

Zeyuan Allen-Zhu
Member, School of Mathematics
November 22, 2016

In this talk I will show how to derive the fastest coordinate descent method [1] and the fastest stochastic gradient descent method [2], both from the linear-coupling framework [3]. I will relate them to linear system solving, conjugate gradient method, the Chebyshev approximation theory, and raise several open questions at the end. No prior knowledge is required on first-order methods.