We study the verification problem in distributed networks, stated as follows. Let $H$ be a subgraph of network $G$ where each vertex knows which edges incident on it are $H$. would like to verify whether has some properties, e.g., if is tree or connected (every node at end process specified property not). perform this decentralized fashion via algorithm. The time complexity measured number rounds communication. In paper we initiate systematic and give almost tight lower bounds running...

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x matrix M and will receive column-vectors of size n, denoted by v1, ..., vn, one one. After seeing each vector vi, we have to output product Mvi before can see next vector. A naive algorithm solve this problem using O(n3) time in total, its running be slightly improved O(n3/log2 n) [Williams SODA'07]. show that a conjecture there is no truly subcubic (O(n3-ε)) for used exhibit underlying polynomial...

A distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on networks with O (log n) bandwidth restriction edges (the standard synchronous CONGEST model). The question whether approximation algorithms help speed up distance computation (more precisely computation) was raised since at least 2004 Elkin (SIGACT News 2004). unweighted case this problem well-understood while its...

While in many graph mining applications it is crucial to handle a stream of updates efficiently terms both time and space, not much was known about achieving such type algorithm. In this paper we study issue for problem which lies at the core called densest subgraph problem. We develop an algorithm that achieves time- space-efficiency simultaneously. It one first its kind problems best our knowledge.

We present a Las Vegas algorithm for dynamically maintaining minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our guarantees O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(1)</sup> ) worst-case update time with high probability. This significantly improves the two recent algorithms by Wulff-Nilsen [2] xmlns:xlink="http://www.w3.org/1999/xlink">0.5-ε</sup> some constant ε > 0 and, independently, Nanongkai...

We consider the classical Minimum Balanced Cut problem: given a graph G, compute partition of its vertices into two subsets roughly equal volume, while minimizing number edges connecting subsets. present first deterministic, almost-linear time approximation algorithm for this problem. Specifically, our algorithm, an n-vertex m-edge G and any parameter 1 ≤ r O(logn), computes (logm) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r2</sup>...

We propose the k -representative regret minimization query ( -regret) as an operation to support multi-criteria decision making. Like top- , -regret assumes that users have some utility or scoring functions; however, it never asks provide such functions. skyline, filters out a set of interesting points from potentially large database based on users' criteria; overwhelms by outputting too many tuples. In particular, for any number and class functions, outputs tuples tries minimize maximum...

We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of network G where each vertex knows which edges incident on it are H. would like to verify whether has some properties, e.g., if is tree or connected (every node end process specified property not). perform this decentralized fashion via algorithm. The time complexity measured number rounds communication.

We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here $n$ is number of nodes in network and $D$ its (hop) diameter. This first non-trivial this problem. It also improves (i) running time randomized $\tilde O(n^{1/2}D^{1/4}+D)$-time Nanongkai [STOC 2014] by factor as large $n^{1/8}$, (ii) $O(\epsilon^{-1}\log \epsilon^{-1})$-approximation...

Motivated by the increasing need for fast distributed processing of large-scale graphs such as Web graph and various social networks, we study a number fundamental problems in message-passing model, where have k machines that jointly perform computation on an arbitrary n-node (typically, n > k) input graph. The is assumed to be randomly partitioned among ≥ 2 (a common implementation many real world systems). communication point-to-point, goal minimize time complexity i.e., rounds, solving...

We present two algorithms for dynamically maintaining a spanning forest of graph undergoing edge insertions and deletions. Our guarantee worst-case update time work against an adaptive adversary, meaning that can depend on previous outputs the algorithms. provide first polynomial improvement over long-standing O(√n) bound [Frederickson STOC'84, Eppstein, Galil, Italiano Nissenzweig FOCS'92] such type The previously best was O(√n (loglogn)2/logn) [Kejlberg-Rasmussen, Kopelowitz, Pettie Thorup...

We present an ~O(m+n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1.5</sup> )-time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, optimal transport) on m-edge, n-node graphs. For moderately dense graphs, i.e. m=Ω(n ), our runs in time nearly linear the input size constitutes first improvement over classic O(m√n)-time [Dinic 1970; Hopcroft-Karp 1971;...

We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+є)-approximate in general graphs with O(poly(logn, 1/є)) update time. (2) an αK approximation of value O(n2/K) time bipartite graphs, every sufficiently large constant positive integer K. Here, 1≤ < 2 is determined by Result first can maintain o(logn)-approximate polylogarithmic time, improving seminal result Onak et al. [STOC 2010]. Its guarantee almost matches best...

We consider questions that arise from the intersection between areas of approximation algorithms, subexponential-time and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for Maximum Clique (Clique) Minimum Dominating Set (DomSet) problems parameterized by size optimal solution. In particular, letting OPT be optimum N input, an runs in t(OPT) poly(N) time outputs...

We study dynamic $(1+\epsilon)$-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected $n$-node $m$-edge graphs under edge deletions. The fastest algorithm this is a randomized with total update time of $\tilde O(mn/\epsilon)$ and constant query by Roditty Zwick [FOCS 2004]. deterministic from 1981 paper Even Shiloach [JACM 1981]; it has $O(mn^2)$ time. improve these results as follows: (1) present an O(n^{5/2}/\epsilon)$ that additive error $2$ addition...

Performing random walks in networks is a fundamental primitive that has found applications many areas of computer science, including distributed computing. In this article, we focus on the problem sampling efficiently network and its applications. Given bandwidth constraints, goal to minimize number rounds required obtain walk samples. All previous algorithms compute sample length ℓ as subroutine always do so naively, is, O (ℓ) rounds. The main contribution article fast algorithm for...

We study the notion of regret ratio proposed in [19] Nanongkai et al. [VLDB10] to deal with multi-criteria decision making database systems. The minimization query was shown have features both skyline and top-k: it does not need information from user but still controls output size. While this approach is suitable for obtaining a reasonably small ratio, open whether one can make arbitrarily small. Moreover, remains reasonable questions be asked users order improve efficiency process.

The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved near-linear time, this is much more challenging even undirected unweighted case. In case, classic O(mn) total update time of Even and Shiloach (JACM 1981) has been fastest known algorithm for three decades. With loss (1 + ε)-approximation factor, running...

We devise new algorithms for the single-source shortest paths (SSSP) problem with non-negative edge weights in CONGEST model of distributed computing. While close-to-optimal solutions, terms number rounds spent by algorithm, have recently been developed computing SSSP approximately, fastest known exact are still far away from matching lower bound Ω (n + D) Peleg and Rubinovich [SIAM Journal on Computing 2000], where n is nodes network D its diameter. The state art Elkin's randomized...

The dynamic matrix inverse problem is to maintain the of a undergoing element and column updates. It main subroutine behind best algorithms for many problems whose complexity not yet well-understood, such as maintaining largest eigenvalue, rank determinant reachability, distances, maximum matching size, k-paths/cycles in graph. Understanding key understand these problems. In this paper, we present (i) improved their extensions some incremental/look-ahead variants, (ii) variants Online...

In the distributed all-pairs shortest paths problem (APSP), every node in weighted undirected network (the CONGEST model) needs to know distance from other using least number of communication rounds (typically called time complexity). The admits (1+o(1))-approximation Θ(n)-time algorithm and a nearly-tight Ω(n) lower bound [Nanongkai, STOC'14; Lenzen Patt-Shamir PODC'15]. For exact case, Elkin [STOC'17] presented an O(n5/3 log2/3 n) bound, which was later improved Õ(n5/4) [Huang, Nanongkai,...

The study of skylines and their variants has received considerable attention in recent years. Skylines are essentially sets most interesting (undominated) tuples a database. However, since the skyline is often very large, much research effort been devoted to identifying smaller subset (say k) "representative skyline" points. Several different definitions representative have considered. Most these formulations intuitive that they try achieve some kind clustering "spread" over entire skyline,...

We consider the problem of performing a random walk in distributed network. Given bandwidth constraints, goal is to minimize number rounds required obtain sample. Das Sarma et al. [PODC'10] show that length l on network diameter D can be performed Õ(√{l D}+D) time. A major question left open whether there exists faster algorithm, especially multiplication √{l} and √{D} necessary.

We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Shortest Paths (SSSP) on $n$-node $m$-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm SSR SSSP goes back three decades to Even Shiloach [JACM 1981]; it has $ O(1) query time O (mn) total update (i.e., linear amortized if all edges are deleted). This serves as a building block several other algorithms. question whether its can be improved is major,...