Spark session: tuesday

Spark Sessions are blocks that include several short plenary “Spark Talks” (15-20 minutes) by laureates. Here they give insights into their current research projects, discuss their work and spark inspiration for new ideas and problem-solving approaches.

Andrei Okounkov: Partition
In both theoretical and applied situations, it is very beneficial to recognize, appreciate, and use the appearance of abstract mathematical structures such as graphs, groups, manifolds, etc. to name just a few examples. In my short talk and the longer class, I would like to advertise adding partitions to your portfolio of mathematical objects. While elementary and combinatorial, partitions form the center around which a lot of advanced mathematics revolves, including many chapters of representation theory, algebraic geometry, and special functions. 

Robert Endre Tarjan: Sorting Using Partial Information
We consider the problem of sorting a set of items having an unknown total order by doing binary comparisons of the items, given the outcomes of some pre-existing comparisons. We present a simple new algorithm with a running time of O(m + n + log T), where n, m, and T are the number of items, the number of pre-existing comparisons, and the number of total orders consistent with the outcomes of the pre-existing comparisons, respectively. The algorithm does O(log T) comparisons. Both our time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been open since 1978. Our algorithm combines two classic algorithms: topological sort and heapsort with the right kind of heap. This is joint work with Bernhard Haeupler, Richard Hladík, John lacono, Vaclay Rozhoi, and Jakub Tětek.