8 citations · 21 across the 13 of their papers we have counts for
15 papers
How to Walk a Dog in Parallel: On Parallel Computation of the Discrete Frechet Distance
Leonid Barenboim, Arnold Filtser, Omrit Filtser +1
The Fréchet distance (also known as the dog-leash distance) is a well-studied and prevalent distance measure for polygonal curves. In this paper we present parallel algorithms for…
Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
Arnold Filtser, Orr Fischer
In the -Proof Labeling Scheme model (-PLS model), our goal is to certify that a network of nodes satisfies a given property . A prover assigns a label to each node, and ea…
The Task Completion Problem and its Application to Crash-Resilient Computation
Orr Fischer, Ran Gelles
We study the Task Completion problem, in which abstract tasks must be completed by a network of crash-prone nodes, where up to nodes may crash for some constant .…
Pointer Chasing with Unlimited Interaction
Orr Fischer, Rotem Oshman, Adi Rosen +1
Pointer-chasing is a central problem in two-party communication complexity: given input size and a parameter , the two players Alice and Bob are given functions $N_A, N_B: […
Two for One, One for All: Deterministic LDC-based Robust Computation in Congested Clique
Keren Censor-Hillel, Orr Fischer, Ran Gelles +1
We design a deterministic compiler that makes any computation in the Congested Clique model robust to a constant fraction of adversarial crash faults. In particular, we show…
All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
Orr Fischer, Merav Parter
Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts th…
Distributed CONGEST Algorithms against Mobile Adversaries
Orr Fischer, Merav Parter
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout t…
Massively Parallel Computation in a Heterogeneous Regime
Orr Fischer, Adi Horowitz, Rotem Oshman
Massively-parallel graph algorithms have received extensive attention over the past decade, with research focusing on three memory regimes: the superlinear regime, the near-linear…
Tree Learning: Optimal Algorithms and Sample Complexity
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein +3
We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collec…
Quantum Distributed Algorithms for Detection of Cliques
Keren Censor-Hillel, Orr Fischer, François Le Gall +2
The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed a…
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen +3
In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the sta…
Superlinear Lower Bounds for Distributed Subgraph Detection
Orr Fischer, Tzlil Gonen, Rotem Oshman
In the distributed subgraph-freeness problem, we are given a graph , and asked to determine whether the network graph contains as a subgraph or not. Subgraph-freeness is an…
On The Multiparty Communication Complexity of Testing Triangle-Freeness
Orr Fischer, Shay Gershtein, Rotem Oshman
In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs.…
Distributed Property Testing for Subgraph-Freeness Revisited
Orr Fischer, Tzlil Gonen, Rotem Oshman
In the subgraph-freeness problem, we are given a constant-size graph , and wish to determine whether the network contains as a subgraph or not. The \emph{property-testing} r…
A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, Juho Hirvonen +5
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires communication rounds, assuming that it finds a correct assignment…