Plenary Lectures

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.

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.

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$.

Knot Floer homology is an invariant for knots in the three-sphere, defined using methods from symplectic goemetry (pseudo-holomorphic curves). Bordered Floer homology is an algebraic approach for counting pseudo-holomorphic curves, introduced in joint work with Robert Lipshitz and Dylan Thurston, originally to study a related three-manifold invariant (Heegaard Floer homology). In this talk, I will present joint work with Zoltan Szabo, in which bordered techniques are used to give efficient computations of knot Floer homology.

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.