Please note: This PhD seminar will take place in DC 1304 and online.
Nathan Harms, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Eric Blais
We study the problem of adjacency sketching for hereditary classes of graphs. The goal is to assign random sketches sk(x) to each vertex x of a graph G from a hereditary class F, in such a way that a decoder who knows the class F but not the specific graph G can decide with high probability over the sketches sk(x) and sk(y) whether vertices x and y are adjacent. Graph classes sketchable in this way are equivalent to communication problems with constant-cost randomized protocols. Our goal is to determine the structural properties of a graph class which allow for constant-size sketches. We suggest that this is the natural probabilistic version of the well-studied adjacency labeling problem in structural graph theory, and our perspective from communication complexity allows for new results on that problem. The problem may also be generalized to certain distance sketching problems.
This talk will survey the work on these problems, including joint works with Sebastian Wild and Viktor Zamaraev (STOC 2022), Louis Esperet and Andrey Kupavskii (RANDOM 2022), and Louis Esperet and Viktor Zamaraev (in submission).