On the possibility of an instance-based complexity theory.

Boaz Barak
Harvard University
April 15, 2019
Worst-case analysis of algorithms has been the central method of theoretical computer science for the last 60 years, leading to great discoveries in algorithm design and a beautiful theory of computational hardness. However, worst-case analysis can be sometimes too rigid, and lead to an discrepancy between the "real world" complexity of a problem and its theoretical analysis, as well as fail to shed light on theoretically fascinating questions arising in connections with statistical physics, machine learning, and other areas.

Etale and crystalline companions

Kiran Kedlaya
University of California, San Diego; Visiting Professor, School of Mathematics
April 15, 2019

Deligne's "Weil II" paper includes a far-reaching conjecture to the
effect that for a smooth variety on a finite field of characteristic p,
for any prime l distinct from p, l-adic representations of the etale
fundamental group do not occur in isolation: they always exist in
compatible families that vary across l, including a somewhat more
mysterious counterpart for l=p (the "petit camarade cristallin"). We
explain in more detail what this all means, indicate some key

The energy functional on Besse manifolds

Marco Radeschi
University of Notre Dame
April 9, 2019

A Riemannian manifold is called Besse, if all of its geodesics are periodic. The goal of this talk is to study the energy functional on the free loop space of a Besse manifold. In particular, we show that this is a perfect Morse-Bott function for the rational, relative, S1-equivariant cohomology of the free loop space. We will show how this result is crucial in proving a conjecture of Berger for spheres of dimension at least 4, although it might be useful for proving the conjecture in full generality.

Space-time correlations at equilibrium

Laure Saint-Raymond
University Paris VI Pierre et Marie Curie and Ecole Normale Supérieure
April 9, 2019
Although the distribution of hard spheres remains essentially chaotic in this regime, collisions give birth to small correlations. The structure of these dynamical correlations is amazing, going through all scales.

    How combinatorial techniques can help to analyze this departure from chaos?

    Bifurcating conformal metrics with constant Q-curvature

    Renato Bettiol
    City University of New York
    April 9, 2019

    The problem of finding metrics with constant Q-curvature in a prescribed conformal class is an important fourth-order cousin of the Yamabe problem. In this talk, I will explain how certain variational bifurcation techniques used to prove non-uniqueness of solutions to the Yamabe problem also yield non-uniqueness results for the constant Q-curvature problem. However, special emphasis will be given to the differences between multiplicity phenomena in these two variational problems. This is based on joint work with P. Piccione and Y. Sire.

    Collective Coin-Flipping Protocols and Influences of Coalitions

    Hamed Hatami
    University of McGill
    April 8, 2019
    The seminal result of Kahn, Kalai and Linial implies that a coalition of a small number of players can bias the outcome of a Boolean function with respect to the uniform measure. We extend this result to arbitrary product measures, by combining their argument with a completely different argument that handles very biased coordinates.

    Disorder increases almost surely.

    Laure Saint-Raymond
    University Paris VI Pierre et Marie Curie and Ecole Normale Supérieure
    April 8, 2019
    Consider a system of small hard spheres, which are initially (almost) independent and identically distributed.

      Then, in the low density limit, their empirical measure $\frac1N \sum_{i=1}^N \delta_{x_i(t), v_i(t)}$ converges
      almost surely to a non reversible dynamics.

        Where is the missing information to go backwards?