Dependent random choice

Jacob Fox
Stanford University
October 26, 2016
We describe a simple yet surprisingly powerful probabilistic technique that shows how to find, in a dense graph, a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently, this technique has had several striking applications, including solutions to a variety of longstanding conjectures of Paul Erdős. In this talk, I will discuss this technique and its diverse applications.

Contesting American Values

Jonathan Israel
Institute for Advanced Study
October 28, 2016
The American Revolution had an enormous, but bitterly divisive impact on European (and Canadian and Latin America) political thought and attitudes. From 1776 began a furious ideological war within the USA over the question of democracy that helped precipitate an even more ferocious conflict between democratic and aristocratic forms of government in Europe. By the 1820s, it seemed that the aristocratic-monarchical system, led by Britain, had finally extinguished "Americanism" everywhere outside the USA.

Communication complexity of approximate Nash equilibria

Aviad Rubinstein
University of California, Berkeley
October 31, 2016

For a constant $\epsilon$, we prove a $\mathrm{poly}(N)$ lower bound on the communication complexity of $\epsilon$-Nash equilibrium in two-player $N \times N$ games. For $n$-player binary-action games we prove an $\exp(n)$ lower bound for the communication complexity of $(\epsilon,\epsilon)$-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least $(1-\epsilon)$-fraction of the players are $\epsilon$-best replying. https://arxiv.org/abs/1608.06580 Joint work with Yakov Babichenko.

Reciprocity laws for torsion classes

Ana Caraiani
October 31, 2016
The law of quadratic reciprocity and the celebrated connection between modular forms and elliptic curves over $\mathbb Q$ are both examples of reciprocity laws. Constructing new reciprocity laws is one of the goals of the Langlands program, which is meant to connect number theory with harmonic analysis and representation theory. In this talk, I will survey some exciting recent progress in establishing new reciprocity laws, namely how to construct Galois representations attached to torsion classes which occur in the cohomology of arithmetic hyperbolic $3$-manifolds.

Settling the complexity of computing approximate two-player Nash equilibria

Aviad Rubinstein
University of California, Berkeley
November 1, 2016
We prove that there exists a constant $\epsilon > 0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $\epsilon$-approximate Nash equilibrium in a two-player ($n \times n$) game requires quasi-polynomial time, $n^{\log^{1-o(1)}n}$. This matches (up to the $o(1)$ term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD.

Lagrangian Whitney sphere links

Ivan Smith
University of Cambridge
November 1, 2016
Let $n > 1$. Given two maps of an $n$-dimensional sphere into Euclidean $2n$-space with disjoint images, there is a $\mathbb Z/2$ valued linking number given by the homotopy class of the corresponding Gauss map. We prove, under some restrictions on $n$, that this vanishes when the components are immersed Lagrangian spheres each with exactly one double point of high Maslov index. This is joint work with Tobias Ekholm.

Riemann-Hilbert correspondence revisited

Yan Soibelman
Kansas State University
November 2, 2016
Conventional Riemann-Hilbert correspondence relates the category of holonomic $D$-modules (de Rham side) with the category of constructible sheaves (Betti side). I am going to reconsider this relationship from the point of view of deformation quantization (on the de Rham side) and Fukaya categories (on the Betti side). Besides of useful re-interpretations of some classical results (e.g.

Counting Galois representations

Frank Calegari
University of Chicago
November 4, 2016
One of the main ideas that comes up in the proof of Fermat's Last Theorem is a way of "counting" 2-dimensional Galois representations over $\mathbb Q$ with certain prescribed properties. We discuss the problem of counting other types of Galois representations, and show how this leads naturally to questions related to derived algebraic geometry and the cohomology of arithmetic groups. A key example will be the case of 1-dimensional representations of a general number field.