39 citations · 135 across the 18 of their papers we have counts for
4 papers · 1 filter
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
Alexandr Andoni, Clifford Stein, Peilin Zhong
We present a -approximate parallel algorithm for computing shortest paths in undirected graphs, achieving depth and $m\mathrm{poly}(\log n)…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin +1
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark are popular systems for processing large amounts of data. The design of efficient algorithms in these framew…
Log Diameter Rounds Algorithms for -Vertex and -Edge Connectivity
Alexandr Andoni, Clifford Stein, Peilin Zhong
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data --- da…