Shaked Matar

activity

20192024

collaborators

5 papers

cs.DS2024

Massively Parallel Algorithms for Approximate Shortest Paths

Michal Dory, Shaked Matar

We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $p o l y (lo g lo g n)$ rounds…

cs.DS2021

Ultra-Sparse Near-Additive Emulators

Michael Elkin, Shaked Matar

Near-additive (aka $(1 + ε, β)$ -) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related…

cs.DC2020

Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work

Elkin Michael, Matar Shaked

We study a $(1 + ε)$ -approximate single-source shortest paths (henceforth, $(1 + ε)$ -SSSP) in $n$ -vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A rand…

cs.DC2019

Fast Deterministic Constructions of Linear-Size Spanners and Skeletons

Michael Elkin, Shaked Matar

In the distributed setting, the only existing constructions of \textit{sparse skeletons}, (i.e., subgraphs with $O (n)$ edges) either use randomization or large messages, or require…

cs.DC2019

Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time

Michael Elkin, Shaked Matar

Given parameters $α \geq 1, β \geq 0$ , a subgraph $G^{'} = (V, H)$ of an $n$ -vertex unweighted undirected graph $G = (V, E)$ is called an $(α, β)$ -spanner if for every pair $u, v \in V$ of vertic…