Vida Dujmović
Title: Adjacency Labelling of Planar Graphs
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.
Ola Svensson
Title: 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(log2 k) compared to an optimal (not necessarily explainable) clustering for the k-medians objective, and a factor of O(k log2 k) for the k-means objective. This improves over the previous best upper bounds of O(k) and O(k2), 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 log2 k), independent of the number of data points n.
This is joint work with Buddhima Gamlath, Xinrui Jia, and Adam Polak.