Plenary Lectures

Link to PDF file All abstracts
Size: 109 kb

    • Shafrira Goldwasser
      MIT, USA
    Pseudo Deterministic Algorithms and Proofs
    Link to PDF file PDF abstract
    Size: 39 kb
    Probabilistic algorithms for both decision and search problems can offer significant complexity improvements over deterministic algorithms. One major difference, however, is that they may output different solutions for different choices of randomness. This makes correctness amplification impossible for search algorithms and is less than desirable in setting where uniqueness of output is important such as generation of system wide cryptographic parameters or distributed setting where different sources of randomness are used. Pseudo-deterministic algorithms are a class of randomized search algorithms, which output a unique answer with high probability. Intuitively, they are indistinguishable from deterministic algorithms by an polynomial time observer of their input/output behavior. In this talk I will describe what is known about pseudo-deterministic algorithms in the sequential, sub-linear and parallel setting. We will also describe n extension of pseudo-deterministic algorithms to interactive proofs for search problems where the verifier is guaranteed with high probability to output the same output on different executions, regardless of the prover strategies.

    • Yuval Peres
      Microsoft Research, USA
    Gravitational allocation on the sphere and overhanging blocks
    Link to PDF file PDF abstract
    Size: 61 kb
    Given $n$ points on the surface of a sphere, how can we partition the sphere fairly among them in an equivariant way? (See Figure 1.) "Fairly" means that each region has the same area. "Equivariant" means that if we rotate the sphere, the solution rotates along with the points. It turns out that if the given points apply a two-dimensional gravity force to the rest of the sphere, then the basins of attraction for the resulting gradient flow yield such a partition—with exactly equal areas, no matter how the points are distributed. Moreover, this partition minimizes, up to a bounded factor, the average distance between points in the same cell. This is joint work with Nina Holden and Alex Zhai. A second topic where potential theory surprisingly appears starts from the classical overhang problem: Given $n$ blocks supported on a table, how far can they be arranged to extend beyond the edge of the table without falling off? With Paterson, Thorup, Winkler and Zwick we showed that an overhang of order $n^{1/3}$ is the best possible; a crucial element in the proof involves an optimal control problem for diffusion on a line segment. In recent work with Laura Florescu and Miklos Racz, we extended the solution of this control problem to higher dimensions, using Green functions and properties of the divisible sandpile established in earlier work with Lionel Levine.

    • Manuel del Pino
      Universidad de Chile
    Singularity formation and bubbling in nonlinear diffusions
    Link to PDF file PDF abstract
    Size: 98 kb
    A fundamental question in nonlinear evolution equations is the analysis of solutions which develop singularities (blow-up) in finite time or as time goes to infinity. We review recent results on the construction of solutions to certain notable nonlinear parabolic PDE which exhibit this kind of behavior in the form of "bubbling". This means solutions that at main order look like asymptotically singular time-dependent scalings of a fixed finite energy entire steady state. We carry out this analysis for the classical two-dimensional harmonic map flow $u_t = \Delta u + |\nabla u|^2u$ into the sphere $S^2$ and the energy-critical semilinear heat equation $u_t = \Delta u + u^{\frac{n+2}{n-2}}$ in ${\bf R}^n$, $n\ge 3$.

    • Peter Ozsvath
      Princeton University, USA
    Link to PDF file PDF abstract
    Size: 26 kb

    • Kannan Soundararajan
      Stanford University, USA
    Recent progress in multiplicative number theory
    Link to PDF file PDF abstract
    Size: 38 kb
    One of the basic themes in number theory is to understand the interplay between the additive and multiplicative structures of the integers. This includes an understanding of prime numbers, and closely related multiplicative functions, such as the Liouville function which keeps track of the parity of the number of prime factors of integers. I will discuss some of the motivations for studying these problems, and report on recent work in the area, including some of my work with Andrew Granville, as well as recent breakthroughs by Harper, Koukoulopoulos, Matomaki, Radziwill, Tao and others.