#### Theory Seminar

# Optimal Compression of Graph Metrics

Add to Google Calendar

p>Every undirected, unweighted graph G=(V,E) defines a "graph metric"

(V,d) where d is the distance function w.r.t. G. Graph spanners,

emulators, and distance oracles can all be viewed as "lossy"

compression schemes that take a (dense) undirected graph G and produce

a representation of some approximation (V,d') of the true metric

(V,d).

What does an information-theoretically optimal compression of (V,d')

look like? In particular, given a budget of n^{1+eps} bits for the

compressed representation, how much must d' diverge from d, as a

function of eps?

In this talk I will survey the history of graph compression. The talk

will cover constructions of additive spanners, sublinear additive

emulators, and a recent lower bound due to Abboud, Bodwin, and Pettie

(arXiv 2016) that mostly closes the problem.