Spanners, i.e. subgraphs which approximately preserve distances, have been studied in both graph and geometric settings for over 25 years. While there has been some limited interaction between researchers working in graph-theoretic settings and researchers working in geometric settings, work in the two communities has generally proceeded in parallel rather than in cooperation. The goal of this workshop is to bring together researchers interested in spanners (and other aspects of distance compression) in order to summarize and explore the state of the art, transition definitions and techniques between the communities, and explore questions about spanners and related objects that are of interest to both communities.

• When?
  Saturday, June 18, 2016.
• Where?
  STOC-SoCG Workshop Day, Cambridge, MA
• What?
  There will be two sessions of talks, one in the morning and one in the afternoon. See the schedule for more details.
• Background?
  All researchers are welcome, although researchers working on spanners are the target audience. We particularly welcome researchers who work in closely related areas such as distance oracles and labels, compact routing schemes, etc.
• Do I need to register?
  No separate registration is required for the workshop.

• 9:00 – 9:15
  Virginia Vassilevska-Williams (Stanford University)
  Welcome
• 9:15 – 9:45
  Shay Solomon (Tel Aviv University)
  A non-geometric approach to geometric spanners

  A geometric (1 + epsilon)-spanner for a point set S in the plane is a sparse subgraph of the complete Euclidean graph corresponding to S, which preserves all pairwise distances to within a factor of 1 + epsilon. This definition can be extended to higher-dimensional Euclidean spaces, and more generally, to metric spaces of low intrinsic dimension.
  
  Geometric spanners have been intensively studied since the mid-80s, with applications ranging from compact routing and distance oracles to robotics and machine learning. In many of these applications, the spanners should achieve additional properties besides sparseness, in particular small weight, degree and (hop-)diameter. Understanding the inherent tradeoffs between these parameters is a fundamental challenge in this area.
  
  In this talk I will discuss novel non-geometric techniques to geometric spanners, and demonstrate their effectiveness in solving several long-standing open questions. The main message of my talk is somewhat surprising -- the right approach to geometric spanners is often non-geometric.

• 9:45 – 10:15
  Fabrizio Grandoni (IDSIA, University of Lugano)
  New Fault-Tolerant Preservers and Spanners

  In this paper we study the existence and computation of sparse (pairwise) f-fault-tolerant (f-FT) preservers and additive spanners, i.e. subgraphs that preserve (exactly or with some small additive error) the distances between given pairs of nodes, under the presence of f edge or vertex failures. We present a variety of results in this setting, including:
  
  (1) The first subquadratic upper bounds on the size of single-source FT preservers in directed and undirected unweighted graphs for any number of faults f. Previously such preservers where known only for $f\leq 2$. Our preservers can also be used to build the first subquadratic-size 2-additive f-FT spanners in undirected unweighted graphs.
  
  (2) A surprising lower-bound construction showing that, for example, any $O(n^{2-\epsilon})$-size spanner needs to have additive stretch at least $\Omega(\epsilon f)$, even to approximately preserve distances for a single pair of nodes in undirected unweighted graphs. This matches asymptotically known upper bounds holding for (all pairs!) f-FT spanners.
  
  (3) Motivated by the above lower bound, we study the case of single-pair preservers in weighted, directed and undirected, graphs. For $f\geq 2$, we give a strong $\Omega(n^2)$ lower bound for the sparsity of any f-FT preserver, that holds for both the directed and the undirected case. Thus, the only non-trivial results possible are in the setting f=1. For undirected weighted graphs we show that for f=1, O(n) edges are both necessary and sufficient, and we prove an extension of this theorem that shows tight bounds for any number of node pairs. For directed graphs, we show that the 1-FT single-pair preserver problem is equivalent to the pairwise preserver problem in the non-faulty setting where $\Theta(n)$ pairs are to be preserved, thus implying that the 1-FT preserver sparsity is between $\Omega(n^{4/3})$ and $O(n^{3/2})$.
  
  Joint work with Greg Bodwin, Merav Parter, and Virginia Vassilevska Williams

• 10:15 – 10:45
  Prosenjit Bose (Carleton University)
  On spanning properties of various Delaunay graphs

  A geometric graph G is a graph whose vertices are points in the plane and whose edges are line segments weighted by the Euclidean distance between their endpoints. In this setting, a t-spanner of G is a connected spanning subgraph G' with the property that for every pair of vertices x, y, the shortest path from x to y in G' has weight at most t ≥ 1 times the shortest path from x to y in G. The parameter t is commonly referred to as the spanning ratio or the stretch factor. Among the many beautiful properties that Delaunay graphs possess, a constant spanning ratio is one of them. We provide an overview of various results concerning the spanning ratio among other properties of different types of Delaunay graphs and their subgraphs.

• 10:45 – 11:10
  Coffee Break
• 11:10 – 12:10
  Santosh Vempala (Georgia Institute of Technology)
  STOC-SoCG Workshop Day Keynote
• 12:10 – 2:00
  Lunch Break
• 2:00– 3:00
  Timothy M. Chan (University of Waterloo)
  STOC-SoCG Workshop Day Keynote
• 3:00 – 3:30
  Coffee Break
• 3:30 – 4:00
  Shiri Chechik (Tel Aviv University)
  Near-Optimal Light Spanners

  A spanner H of a weighted undirected graph G is a "sparse" subgraph that approximately preserves distances between every pair of vertices in G. We refer to H as a k-spanner (or as a spanner with stretch k) of G for some parameter k if the distance in H between every vertex pair is at most a factor k bigger than in G. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). It is well-known that for any positive integer k, one can efficiently construct a (2k-1)-spanner of G with O(n^{1+1/k}) edges where n is the number of vertices [Althöfer et al. 93]. This size-stretch tradeoff is conjectured to be optimal based on a girth conjecture of Erdös. However, the current state of the art for the second measure is not yet optimal. In this talk I am going to discuss a construction for spanners with near optimal bounds with respect to the stretch, the weight and the number of edges. Based on a joint work with Christian Wulff-Nilsen.

• 4:00 – 4:30
  Ljubomir Perkovic (Depaul University)
  Spanners via p-gon distance Delaunay triangulations

  What is the smallest maximum degree that can always be achieved for a plane (i.e., with no crossing edges) spanner of a complete Euclidean graph? This is a fundamental question and the Delaunay triangulation, a well-known plane spanner, is a natural starting point for attempts to answer it. Delaunay triangulations have, however, proven difficult to work with. Recent progress on answering the question has relied instead on Delaunay triangulations defined using alternative distance functions. Rather than using the standard Euclidean distance based on a circle, those Delaunay triangulations are defined using distances based on (regular) p-gons.
  
  Delaunay triangulations defined using p-gon distances have local structural properties that make them amenable to analysis. In addition to their use in bounding the degree of plane spanners, they have been used in developing geometric routing schemes. They may also help in tackling the question of determining the exact spanning ratio (i.e., stretch factor) of Delaunay triangulations. Over the past 30 years, there has been intense interest in computing the exact spanning ratio of classic (circle distance) Delaunay triangulations. Despite that, until recently the only type of Delaunay triangulation for which the answer has been known is the triangle distance Delaunay triangulation (Chew '89). It is likely that work on the spanning ratio of p-gon distance Delaunay triangulations will build the bridge leading to a better understanding of the spanning ratio of classic Delaunay triangulations.
  
  In this talk, I will review a selection of recent work that rely on p-gon distance Delaunay triangulations and highlight some of their properties as well as techniques that have been developed.

• 4:30 – 5:00
  Greg Bodwin (Stanford University)
  Understanding Additive Spanners via Distance Preservers

  An Additive Spanner of a graph is a sparse subgraph that preserves all pairwise distances within +k error. A Distance Preserver of a graph is a sparse subgraph that exactly preserves pairwise distances within a small set P of node pairs. There have been several recent successful lines of research that have converted existing knowledge of distance preservers into a new understanding of additive spanners. In this talk, we will discuss some of the results and techniques used in this line of attack. In particular, we will overview the recent result (to appear in STOC '16) that there are no additive spanner constructions with +n^{o(1)} error and n^{4/3 - eps} edges (which is proved by reduction to distance preserver lower bounds). We will also survey some of the major results and open questions in distance preservers research, and demonstrate further relationships between these problems and some of the major remaining questions in additive spanners research.

• 5:00 – 5:30
  Wolfgang Mulzer (Freie Universität Berlin)
  Efficient Spanner Construction for Directed Transmission Graphs

  Let P be a set of n points in the plane, each with an associated radius r(p) > 0. The transmission graph G for P has vertex set P and a directed edge from p to q if and only if q lies in the ball with radius r(p) around p.
  
  Let t > 1. A t-spanner H for G is a sparse subgraph such that for any two vertices p and q connected by a path of length l in G, there is a path of length at most tl from p to q in H. Given G implicitly as points with radii, we show how to compute a t-spanner for G in time O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius in P. Furthermore, we extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a bonus, it turns out that the properties of our spanner also allow us to compute a BFS tree for G and any given start vertex s in the same time.
  
  Based on joint work with Haim Kaplan, Liam Roditty and Paul Seiferth.

• 5:30 – 6:00
  Michael Dinitz (Johns Hopkins University)
  Approximating Spanners

  This talk will survey recent work on approximating spanners, in which we consider the computational problem of finding the "best" spanner given an input graph. This is in contrast to the study of "universal" bounds, i.e. bounds on spanner size/quality which hold universally for all (or a defined subclass) of graphs. We will see that in some cases we can give approximation bounds even when universal bounds do not exist, and when universal bounds do exist we can sometimes optimize to find even better spanners (if they exist).

• Shiri Chechik, Tel Aviv University
• Michael Dinitz, Johns Hopkins University
• Virginia Vassilevska Williams, Stanford University