אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We develop a new approach for distributed distance computation in planar graphs that is based on a variant of the metric compression problem recently introduced by Abboud et al. [SODA'18]. In our variant of the Planar Graph Metric Compression Problem, one is given an $n$-vertex planar graph $G=(V,E)$, a set of $S \subseteq V$ source terminals lying on a single face, and a subset of target terminals $T \subseteq V$. The goal is to compactly encode the $S\times T$ distances.

One of our key technical contributions is in providing a compression scheme that encodes all $S \times T$ distances using $\widetilde{O}(|S|\cdot\poly(D)+|T|)$ bits\footnote{As standard, $\widetilde{O}$ is used to hide $\poly\log n$ factors.}, for unweighted graphs with diameter $D$. This significantly improves the state of the art of $\widetilde{O}(|S|\cdot 2^{D}+|T| \cdot D)$ bits. We also consider an approximate version of the problem for \emph{weighted} graphs, where the goal is to encode $(1+\epsilon)$ approximation of the $S \times T$ distances, for a given input parameter $\epsilon \in (0,1]$. Here, our compression scheme uses $\widetilde{O}(\poly(|S|/\epsilon)+|T|)$ bits. In addition, we describe how these compression schemes can be computed in near-linear time. At the heart of this compact compression scheme lies a VC-dimension type argument on planar graphs, using the well-known Sauer’'s lemma.

This efficient compression scheme leads to several improvements and simplifications in the setting of diameter computation, most notably in the distributed setting:
- There is an $\widetilde{O}(D^5)$-round randomized distributed algorithm for computing the diameter in planar graphs, w.h.p.
- There is an $\widetilde{O}(D^3)+\poly(\log n/\epsilon)\cdot D^2$-round randomized distributed algorithm for computing an $(1+\epsilon)$ approximation of the diameter in weighted graphs with polynomially bounded weights, w.h.p. No sublinear round algorithms were known for these problems before.

Joint work with Jason Li, to appear in STOC'19.