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.

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?

        Two-dimensional random field Ising model at zero temperature

        Jian Ding
        The Wharton School, The University of Pennsylvania
        April 5, 2019
        I will discuss random field Ising model on $Z^2$ where the external field is given by i.i.d. Gaussian
        variables with mean zero and positive variance. I will present a recent result that at zero temperature the effect of boundary conditions on the magnetization in a finite box decays exponentially in the distance to the boundary. This is based on joint work with Jiaming Xia.