# Plenary Lectures

• Shafrira Goldwasser
MIT, USA
Pseudo Deterministic Algorithms and Proofs
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
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
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$.
• • 