Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
387
0
0.0
(
0
)
Added by
Maximilian Probst Gutenberg
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. This paper develops fast dynamic algorithms for sparse spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. Under the popular OMv conjecture, we show that there can be no decremental or incremental algorithm that maintains an $n^{1+o(1)}$ edge (purely additive) $+n^{delta}$-emulator for any $delta<1/2$ with arbitrary polynomial preprocessing time and total update time $m^{1+o(1)}$. Also, under the Combinatorial $k$-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an $n^{1+o(1)}$ edge $(1+epsilon,n^{o(1)})$-spanner or emulator must either have preprocessing time $mn^{1-o(1)}$ or amortized update time $m^{1-o(1)}$. Both of our conditional lower bounds are tight. As the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the $m^{1-o(1)}$ update time for dense graphs. For any constant $epsilonin (0,1]$, there is a fully dynamic algorithm with worst-case update time $O(n^{1.529})$ that whp maintains an $n^{1+o(1)}$ edge $(1+epsilon,n^{o(1)})$-spanner. Our new algebraic techniques and spanner algorithms allow us to also obtain (1) a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) with update and path query time $O(n^{1.9})$; (2) a fully dynamic $(1+epsilon)$-approximate APSP algorithm with update time $O(n^{1.529})$; (3) a fully dynamic algorithm for near-$2$-approximate Steiner tree maintenance.
rate research
Read More
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system $(A,b)$, for $A in mathbb{R}^{n times n}$ and $b in mathbb{R}^n$, we wish to find a vector $x in mathbb{R}^n$ such that $Ax = b$. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time $O(n^{omega})$. We consider the problem of finding $varepsilon$-approximate solutions to linear systems with respect to the $L_2$-norm, that is, given a satisfiable linear system $(A in mathbb{R}^{n times n}, b in mathbb{R}^n)$, find an $x in mathbb{R}^n$ such that $||Ax - b||_2 leq varepsilon||b||_2$. Our main result is a fine-grained reduction from computing the rank of a matrix to finding $varepsilon$-approximate solutions to linear systems. In particular, if the best known $O(n^omega)$ time algorithm for computing the rank of $n times O(n)$ matrices is optimal (which we conjecture is true), then finding an $varepsilon$-approximate solution to a dense linear system also requires $tilde{Omega}(n^{omega})$ time, even for $varepsilon$ as large as $(1 - 1/text{poly}(n))$. We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices, well-conditioned linear systems, and approximately solving linear systems with respect to the $L_p$-norm, for $p geq 1$. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity.
There has been a resurgence of interest in lower bounds whose truth rests on the conjectured hardness of well known computational problems. These conditional lower bounds have become important and popular due to the painfully slow progress on proving strong unconditional lower bounds. Nevertheless, the long term goal is to replace these conditional bounds with unconditional ones. In this paper we make progress in this direction by studying the cell probe complexity of two conjectured to be hard problems of particular importance: matrix-vector multiplication and a version of dynamic set disjointness known as Patrascus Multiphase Problem. We give improved unconditional lower bounds for these problems as well as introducing new proof techniques of independent interest. These include a technique capable of proving strong threshold lower bounds of the following form: If we insist on having a very fast query time, then the update time has to be slow enough to compute a lookup table with the answer to every possible query. This is the first time a lower bound of this type has been proven.
The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the ones that follow from trivial recomputation after each update or from solving dynamic All-Pairs Shortest Paths (APSP), which is very computationally intensive. This is the situation for dynamic approximation algorithms as well, and even if only edge insertions or edge deletions need to be supported. This paper provides a comprehensive study of the dynamic approximation of Diameter, Radius and Eccentricities, providing both conditional lower bounds, and new algorithms whose bounds are optimal under popular hypotheses in fine-grained complexity. Some of the highlights include: - Under popular hardness hypotheses, there can be no significantly better fully dynamic approximation algorithms than recomputing the answer after each update, or maintaining full APSP. - Nearly optimal partially dynamic (incremental/decremental) algorithms can be achieved via efficient reductions to (incremental/decremental) maintenance of Single-Source Shortest Paths. For instance, a nearly $(3/2+epsilon)$-approximation to Diameter in directed or undirected graphs can be maintained decrementally in total time $m^{1+o(1)}sqrt{n}/epsilon^2$. This nearly matches the static $3/2$-approximation algorithm for the problem that is known to be conditionally optimal.
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the $k$-XOR problem. Specifically, we define MaxSP as the class of problems definable as $max_{x_1,dots,x_k} #{ (y_1,dots,y_ell) : phi(x_1,dots,x_k, y_1,dots,y_ell) }$, where $phi$ is a quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On $m$-sized structures, we can solve each such problem in time $O(m^{k+ell-1})$. Our results are: - We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under *deterministic* fine-grained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of $O(m^{k+ell-1})$ for *all* problems in MaxSP/MinSP by a polynomial factor. - This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic $c$-approximation would give a $(c+varepsilon)$-approximation for all MaxSP/MinSP problems in time $O(m^{k+ell-1-delta})$, where $varepsilon > 0$ can be chosen arbitrarily small. Combining our completeness with~(Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is *equivalent* to giving a $O(1)$-approximation for all MinSP problems in faster-than-$O(m^{k+ell-1})$ time.
A emph{spanner} of a graph $G$ is a subgraph $H$ that approximately preserves shortest path distances in $G$. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured emph{multiplicatively}. In this work, we investigate whether one can similarly extend constructions of spanners with purely emph{additive} error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic $+2$ and $+4$ unweighted spanners (both all-pairs and pairwise) to $+2W$ and $+4W$ weighted spanners, where $W$ is the maximum edge weight. Specifically, we show that a weighted graph $G$ contains all-pairs (pairwise) $+2W$ and $+4W$ weighted spanners of size $O(n^{3/2})$ and $widetilde{O}(n^{7/5})$ ($O(np^{1/3})$ and $O(np^{2/7})$) respectively. For a technical reason, the $+6$ unweighted spanner becomes a $+8W$ weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that $G$ contains all-pairs (pairwise) $+8W$ weighted spanners of size $O(n^{4/3})$ ($O(np^{1/4})$).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
