Given a directed graph G = (V, E) on n vertices and m edges, a subgraph H = (V, Eʹ ⊆ E) is defined to be a t-diameter spanner if the diameter of H is at most t times the diameter of G. We show the existence of (and algorithms to compute) various t-diameter spanners with a sparse set of edges and t < 2, for directed graphs. In addition, we show that our spanner constructions give tight bounds on the number of edges. To the best of our knowledge, our work is the first to focus on the existence of various sparse (with ≪ n2 edges) diameter spanners of stretch < 2, for directed graphs. We also study eccentricity spanner, which is a subgraph that approximately preserves all vertex eccentricities of the original graph. As an application of our eccentricity spanner construction, we obtain the first Õ(m)-time algorithm for computing 2-approximation of vertex eccentricities in general directed graphs. This improves the result of Backurs et al. [STOC 2018] who gave an time algorithm for this problem, and showed that there is no O(n2−o(1)) time algorithm that achieves approximation better than 2, unless SETH fails; this shows that our approximation factor is essentially tight. Finally, we study extremal distance spanners under dynamic settings. For dynamic diameter spanners, we provide incremental and decremental algorithms with a subquadratic total update time. For dynamic eccentricities and eccentricity spanner, we provide incremental and decremental algorithms with (2+ε)-approximation and O(n1+o(1)) amortized update time.

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology. Consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points inX= Rdare long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional cased= 1, which is perhaps one of the most used in practice. In this article, we break the nearly 50-year-old quadratic time bound for computing DTW or GED between two sequences ofnpoints in R by presenting deterministic algorithms that run inO(n2log log logn/ log logn) time. Our algorithms can be extended to work also for higher-dimensional spaces Rd, for any constantd, when the underlying distance-metric dist is polyhedral (e.g.,L1,Linfin).

Given a set of $n$ real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Grønlund and Pettie [FOCS'14], a simple $Θ(n^2)$-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as $k$-SUM and $k$-variate linear degeneracy testing ($k$-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P. In this paper, we show that the randomized $4$-linear decision tree complexity of 3SUM is $O(n^{3/2})$, and that the randomized $(2k-2)$-linear decision tree complexity of $k$-SUM and $k$-LDT is $O(n^{k/2})$, for any odd $k\ge 3$. These bounds improve (albeit randomized) the corresponding $O(n^{3/2}\sqrt{\log n})$ and $O(n^{k/2}\sqrt{\log n})$ decision tree bounds obtained by Grønlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in $O(n^2 \log\log n / \log n )$ time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of word-RAM model.

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology, consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in X = R^d are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case d = 1, which is perhaps one of the most used in practice. In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of n points in R, by presenting deterministic algorithms that run in O( n^2 log log log n / log log n ) time. Our algorithms can be extended to work also for higher dimensional spaces R^d, for any constant d, when the underlying distance-metric dist is polyhedral (e.g., L_1, L_infty).

Given a set $S$ of $n$ points in \mathbb{R}^d, the Closest Pair problem is to find a pair of distinct points in S at minimum distance. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We consider the high-dimensional L_\infty Closest Pair problem, where d=n^r for some r > 0, and the underlying metric is L_\infty. We improve and simplify previous results for L_\infty Closest Pair, showing that it can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)\log n) time, and by a randomized algorithm that runs in O(DP(n,d)) expected time, where DP(n,d) is the time bound for computing the dominance product for n points in \mathbb{R}^d. That is a matrix D, such that D[i,j] = \bigl| \{k \mid p_i[k] \leq p_j[k]\} \bigr|; this is the number of coordinates at which p_j dominates p_i. For integer coordinates from some interval [-M, M], we obtain an algorithm that runs in \tilde{O}\left(\min\{Mn^{\omega(1,r,1)},\, DP(n,d)\}\right) time, where \omega(1,r,1) is the exponent of multiplying an n \times n^r matrix by an n^r \times n matrix. We also give slightly better bounds for DP(n,d), by using more recent rectangular matrix multiplication bounds. Computing the dominance product itself is an important task, since it is applied in many algorithms as a major black-box ingredient, such as algorithms for APBP (all pairs bottleneck paths), and variants of APSP (all pairs shortest paths).

Communication networks are vulnerable to natural disasters, such as earthquakes or floods, as well as to physical attacks, such as an Electromagnetic Pulse (EMP) attack. Such real-world events happen at specific geographical locations and disrupt specific parts of the network. Therefore, the geographical layout of the network determines the impact of such events on the network's connectivity. Recent works focused on assessing the vulnerability of a deterministic (geographical) network to such events. Here, we focus on assessing the vulnerability of (geographical) random networks to such disasters and identifying the most vulnerable parts of a network where only partial (probabilistic) information about its geographical layout is given. We consider stochastic models in which nodes and links are probabilistically distributed geographically on a plane, and model the disaster event as a circular cut that destroys any node or link within or intersecting the circle. We develop algorithms for assessing the damage of such attacks and determining which attack locations have the most disruptive impact on the network. Our novel approach allows identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using stochastic modeling and geometric probability techniques can significantly contribute to our understanding of network survivability and resilience.