92 citations · 170 across the 35 of their papers we have counts for
25 papers · 1 filter
Distributed Stochastic Graph Algorithms
Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis
We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph of a known base graph is realize…
Witness-Sensitive Detection of Induced Diamonds
Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams +1
We provide a fast \emph{witness-sensitive} algorithm for detecting an induced diamond (a minus an edge) in an -vertex graph containing induced diamonds. Our algorithm…
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…
Computing in a Faulty Congested Clique
Keren Censor-Hillel, Pedro Soto
We study a Faulty Congested Clique model, in which an adversary may fail nodes in the network throughout the computation. We show that any task of -bit input per node…
Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate -clique counts faster
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
Dell, Lapinskas and Meeks [DLM SICOMP 2022] presented a general reduction from approximate counting to decision for a class of fine-grained problems that can be viewed as hyperedge…
Near-Optimal Resilient Labeling Schemes
Keren Censor-Hillel, Einav Huberman
Labeling schemes are a prevalent paradigm in various computing settings. In such schemes, an oracle is given an input graph and produces a label for each of its nodes, enabling the…
Fast Approximate Counting of Cycles
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a $(1…
Faster Cycle Detection in the Congested Clique
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
We provide a fast distributed algorithm for detecting -cycles in the \textsf{Congested Clique} model, whose running time decreases as the number of -cycles in the graph incre…
Distributed Subgraph Finding: Progress and Challenges
Keren Censor-Hillel
This is a survey of the exciting recent progress made in understanding the complexity of distributed subgraph finding problems. It overviews the results and techniques for assorted…
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…
Distributed Vertex Cover Reconfiguration
Keren Censor-Hillel, Yannic Maus, Shahar Romem-Peled +1
Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most r…
Locally Checkable Labelings with Small Messages
Alkida Balliu, Keren Censor-Hillel, Yannic Maus +2
A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we s…
Fault Tolerant Max-Cut
Keren Censor-Hillel, Noa Marelly, Roy Schwartz +1
In this work, we initiate the study of fault tolerant Max Cut, where given an edge-weighted undirected graph , the goal is to find a cut that maximizes the…
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…
Distributed Approximation on Power Graphs
Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus +2
We investigate graph problems in the following setting: we are given a graph and we are required to solve a problem on . While we focus mostly on exploring this theme in t…
Hardness of Distributed Optimization
Nir Bachrach, Keren Censor-Hillel, Michal Dory +3
This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing $\t…
Erasure Correction for Noisy Radio Networks
Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz +1
The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. T…
Distributed Spanner Approximation
Keren Censor-Hillel, Michal Dory
We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and ha…
Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model
Keren Censor-Hillel, Dean Leitersdorf, Elia Turner
We multiply two matrices over semirings in the Congested Clique model, where fully connected nodes communicate synchronously using -bit messages,…
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion
Amir Abboud, Keren Censor-Hillel, Seri Khoury +1
We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of \emph{fooling views} and exemplify its strength by…
Fast Distributed Approximation for TAP and 2-Edge-Connectivity
Keren Censor-Hillel, Michal Dory
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph and a spanning tree for it, and the goal is to augment with a…
Fast Distributed Approximation for Max-Cut
Keren Censor-Hillel, Rina Levy, Hadas Shachnai
Finding a maximum cut is a fundamental task in many computational settings. Surprisingly, it has been insufficiently studied in the classic distributed settings, where vertices com…
Making Asynchronous Distributed Computations Robust to Noise
Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interac…
Distributed Construction of Purely Additive Spanners
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz +1
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases.…