research
∙
09/13/2023
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
We study a new and stronger notion of fault-tolerant graph structures wh...
share
research
∙
07/12/2023
Connectivity Labeling for Multiple Vertex Failures
We present an efficient labeling scheme for answering connectivity queri...
research
∙
05/23/2023
Distributed CONGEST Algorithms against Mobile Adversaries
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the stud...
research
∙
11/17/2022
Near-Optimal Distributed Computation of Small Vertex Cuts
We present near-optimal algorithms for detecting small vertex cuts in th...
research
∙
11/13/2022
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Hopsets and spanners are fundamental graph structures, playing a key rol...
research
∙
09/07/2022
Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel
We (nearly) settle the time complexity for computing vertex fault-tolera...
research
∙
08/22/2022
Õptimal Dual Vertex Failure Connectivity Labels
In this paper we present succinct labeling schemes for supporting connec...
research
∙
12/10/2021
Improved Deterministic (Δ+1)-Coloring in Low-Space MPC
We present a deterministic O(logloglog n)-round low-space Massively Para...
research
∙
11/25/2021
New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the √(n) Barrier
For an n-vertex digraph G=(V,E), a shortcut set is a (small) subset of e...
research
∙
06/03/2021
Low-Congestion Shortcuts in Constant Diameter Graphs
Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016...
research
∙
06/03/2021
Component Stability in Low-Space Massively Parallel Computation
We study the power and limitations of component-stable algorithms in the...
research
∙
06/01/2021
Fault-Tolerant Labeling and Compact Routing Schemes
The paper presents fault-tolerant (FT) labeling schemes for general grap...
research
∙
02/19/2021
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt ...
research
∙
10/04/2020
Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers
Fault tolerant distance preservers (spanners) are sparse subgraphs that ...
research
∙
10/03/2020
Spiking Neural Networks Through the Lens of Streaming Algorithms
We initiate the study of biological neural networks from the perspective...
research
∙
09/13/2020
Simple, Deterministic, Constant-Round Coloring in the Congested Clique
We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring p...
research
∙
08/12/2020
Deterministic Replacement Path Covering
In this article, we provide a unified and simplified approach to derando...
research
∙
06/12/2020
On Packing Low-Diameter Spanning Trees
Edge connectivity of a graph is one of the most fundamental graph-theore...
research
∙
04/14/2020
Round-Efficient Distributed Byzantine Computation
We present the first round efficient algorithms for several fundamental ...
research
∙
03/06/2020
Exponentially Faster Shortest Paths in the Congested Clique
We present improved deterministic algorithms for approximating shortest ...
research
∙
12/24/2019
Planar Diameter via Metric Compression
We develop a new approach for distributed distance computation in planar...
research
∙
12/11/2019
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
The Massively Parallel Computation (MPC) model is an emerging model whic...
research
∙
08/08/2019
Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
We revisit classical connectivity problems in the CONGEST model of distr...
research
∙
07/26/2019
New (α,β) Spanners and Hopsets
An f(d)-spanner of an unweighted n-vertex graph G=(V,E) is a subgraph H ...
research
∙
04/25/2019
Winner-Take-All Computation in Spiking Neural Networks
In this work we study biological neural networks from an algorithmic per...
research
∙
04/16/2019
Parallel Balanced Allocations: The Heavily Loaded Case
We study parallel algorithms for the classical balls-into-bins problem, ...
research
∙
02/27/2019
Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons
We consider the task of measuring time with probabilistic threshold gate...
research
∙
02/21/2019
Local Computation Algorithms for Spanners
A graph spanner is a fundamental graph structure that faithfully preserv...
research
∙
12/28/2018
The Power of Distributed Verifiers in Interactive Proofs
We explore the power of interactive proofs with a distributed verifier. ...
research
∙
12/09/2018
Low Congestion Cycle Covers and their Applications
A cycle cover of a bridgeless graph G is a collection of simple cycles i...
research
∙
05/14/2018
Congested Clique Algorithms for Graph Spanners
Graph spanners are sparse subgraphs that faithfully preserve the distanc...
research
∙
05/07/2018
(Δ+1) Coloring in the Congested Clique Model
In this paper, we present improved algorithms for the (Δ+1) (vertex) col...
research
∙
02/20/2018
Wireless Expanders
This paper introduces an extended notion of expansion suitable for radio...
research
∙
12/04/2017
Distributed Computing Made Secure: A New Cycle Cover Theorem
In the area of distributed graph algorithms a number of network's entiti...
research
∙
06/05/2017
Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks
We study distributed algorithms implemented in a simplified biologically...
research
∙
10/06/2016