## Vida Dujmović

## Title: Adjacent Labelling of Planar Graphs (and Beyond)

## Abstract:

Adjacency labelling schemes, which have been studied since the 1980s, ask for short labels for n-vertex graphs G such that the labels of two vertices u and v are sufficient to determine (quickly) if uv is an edge of G. One of the long-standing problems in the area was the optimal length of labels for planar graphs. The problem is closely related to the size of the smallest universal graph for all n-vertex planar graphs. In this talk I will show how we resolved this problem (up to lower order terms) with the help of a new graph theoretic tool: a product-structure theorem for planar graphs. This new tool and our result are applicable not only to planar graphs but also to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

## Svensson Ola

## Title: Nearly-Tight and Oblivious Algorithms for Explainable Clustering

## Abstract:

An important topic in current machine learning research is to explain and/or interpret how models actually make their decisions. Motivated by this, Moshkovitz, Dasgupta, Rashtchian, and Frost recently formalized the problem of explainable clustering. A k-clustering is said to be explainable if it is given by a decision tree where each internal node splits data points with a threshold cut in a single dimension (feature), and each of the k leaves corresponds to a cluster.

In this talk, we see an algorithm that outputs an explainable clustering that loses at most a factor of O(log^{2} k) compared to an optimal (not necessarily explainable) clustering for the k-medians objective, and a factor of O(k log^{2} k) for the k-means objective. This improves over the previous best upper bounds of O(k) and O(k^{2}), respectively, and nearly matches the previous Ω(log k) lower bound for k-medians and our new Ω(k) lower bound for k-means. Moreover, the algorithm is remarkably simple and, given an initial not necessarily explainable clustering, it is oblivious to the data points and runs in time O(dk log^{2} k), independent of the number of data points n.

This is joint work with Buddhima Gamlath, Xinrui Jia, and Adam Polak.