Arrow Research search

Author name cluster

Keren Censor-Hillel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
2 author rows

Possible papers

13

SODA Conference 2021 Conference Paper

Tight Distributed Listing of Cliques

  • Keren Censor-Hillel
  • Yi-Jun Chang
  • François Le Gall
  • Dean Leitersdorf

Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributed computing. However, so far, very few tight bounds are known in this area. For triangle (i. e. , 3-clique) listing, an optimal Õ ( n 1/3 )-round distributed algorithm has been constructed by Chang et al. [SODA 2019, PODC 2019]. Recent works of Eden et al. [DISC 2019] and of Censor-Hillel et al. [PODC 2020] have shown sublinear algorithms for K p -listing, for each p ≥ 4, but still leaving a significant gap between the upper bounds and the known lower bounds of the problem. In this paper, we completely close this gap. We show that for each p ≥ 4, there is an Õ ( n 1–2/ p )-round distributed algorithm that lists all p -cliques K p in the communication network. Our algorithm is optimal up to a polylogarithmic factor, due to the -round lower bound of Fischer et al. [SPAA 2018], which holds even in the CONGESTED CLIQUE model. Together with the triangle-listing algorithm by Chang et al. [SODA 2019, PODC 2019], our result thus shows that the round complexity of K p -listing, for all p, is the same in both the CONGEST and CONGESTED CLIQUE models, at rounds. For p = 4, our result additionally matches the lower bound for K 4 - detection by Czumaj and Konrad [DISC 2018], implying that the round complexities for detection and listing of K 4 are equivalent in the CONGEST model.

Details

TCS Journal 2020 Journal Article

Approximate proof-labeling schemes

  • Keren Censor-Hillel
  • Ami Paz
  • Mor Perry

We study a new model of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PLS) model defines a distributed proof in the form of a label that is given to each node, and all nodes locally verify that the network configuration satisfies the desired boolean predicate by exchanging labels with their neighbors. The proof size of the scheme is defined to be the maximum size of a label. In this work, we extend this model by defining the approximate proof-labeling scheme (APLS) model. In this new model, the predicates for verification are of the form ψ ≤ φ, where ψ, φ: F → N for a family of configurations F. Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration α, so that only if ψ > α φ some node must reject. We focus on two verification problems: upper and lower bounds on the diameter of the graph, and the maximality of a given matching. For these problems, we present the first results that apply to all graph structures. In our new APLS model, we show that the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size. Finally, we present the first general result for maximum cardinality matching in the PLS model.

Details DOI

TCS Journal 2020 Journal Article

Sparse matrix multiplication and triangle listing in the Congested Clique model

  • Keren Censor-Hillel
  • Dean Leitersdorf
  • Elia Turner

We show how to multiply two n × n matrices S and T over semirings in the Congested Clique model, where n nodes communicate in a fully connected synchronous network using O ( log ⁡ n ) -bit messages, within O ( n z ( S ) 1 / 3 n z ( T ) 1 / 3 / n + 1 ) rounds of communication, where n z ( S ) and n z ( T ) denote the number of non-zero elements in S and T, respectively. By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication costs compared with general multiplication algorithms [Censor-Hillel et al. (2015) [9]], and thus improves upon the state-of-the-art for matrices with o ( n 2 ) non-zero elements. Moreover, our algorithm exhibits the additional strength of surpassing previous solutions also in the case where only one of the two matrices is such. Particularly, this allows to efficiently raise a sparse matrix to a power greater than 2. As applications, we show how to speed up the computation on non-dense graphs of 4-cycle counting and all-pairs-shortest-paths. Our algorithmic contribution is a new deterministic method of restructuring the input matrices in a sparsity-aware manner, which assigns each node with element-wise multiplication tasks that are not necessarily consecutive but guarantee a balanced element distribution, providing for communication-efficient multiplication. Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster deterministic solutions for graph related problems. As an example, we present a new sparsity aware, deterministic algorithm which solves the triangle listing problem in O ( m / n 5 / 3 + 1 ) rounds, a complexity that was previously obtained by a randomized algorithm [Pandurangan et al. (2018) [26]], and that matches the known lower bound of Ω ˜ ( n 1 / 3 ) when m = n 2 of [Izumi and Le Gall (2017) [19], Pandurangan et al. (2018) [26]]. Naturally, our triangle listing algorithm also implies triangle counting within the same complexity of O ( m / n 5 / 3 + 1 ) rounds, which is (possibly more than) a cubic improvement over the previously known deterministic O ( m 2 / n 3 ) -round algorithm [Dolev et al. (2012) [12]].

Details DOI

TCS Journal 2020 Journal Article

The sparsest additive spanner via multiple weighted BFS trees

  • Keren Censor-Hillel
  • Ami Paz
  • Noam Ravid

Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known ( + 6 ) -spanner constructions are essentially the sparsest possible, that is, larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. Distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing ( + 2 ) and ( + 4 ) -all-pairs spanners, the sparsest case of ( + 6 ) -spanners remained elusive. We remedy this by designing a new sequential algorithm for constructing a ( + 6 ) -spanner with the essentially-optimal sparsity of O ˜ ( n 4 / 3 ) edges. We then show a distributed implementation of our algorithm, answering an open problem in [12]. A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in | S | + D − 1 rounds, where S is the set of sources and D is the diameter of the network graph.

Details DOI

TCS Journal 2018 Journal Article

On fast and robust information spreading in the Vertex-Congest model

  • Keren Censor-Hillel
  • Tariq Toukan

This paper initiates the study of the impact of failures on the fundamental problem of information spreading in the Vertex-Congest model, in which in every round, each of the n nodes sends the same O ( log ⁡ n ) -bit message to all of its neighbors. We consider a strong failure model, in which links are reliable but nodes fail independently with probability q per round and never recover. Our contribution to coping with failures is twofold. First, we prove that the randomized algorithm which chooses uniformly at random the next message to forward is slow, requiring Ω ( n / k ) rounds on some graphs, which we denote by G n, k, where k is the vertex-connectivity. Second, we design a randomized algorithm that makes dynamic message choices, with probabilities that change over the execution. We prove that for G n, k it requires only a near-optimal number of O ( n log 3 ⁡ n / k ) rounds, despite a rate of q = O ( k / n log 3 ⁡ n ) failures per round. Our technique of choosing probabilities that change according to the execution is of independent interest.

Details DOI

SODA Conference 2014 Conference Paper

A New Perspective on Vertex Connectivity

  • Keren Censor-Hillel
  • Mohsen Ghaffari 0001
  • Fabian Kuhn

Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are the classical results of Tutte and Nash-Williams from 1961 which show that a λ -edge-connected graph contains ⌊( λ − 1)/2⌋ edge-disjoint spanning trees. We argue that connected dominating set partitions and packings are the natural analogues of edge-disjoint spanning trees in the context of vertex connectivity and we use them to obtain structural results about vertex connectivity in the spirit of those for edge connectivity. More specifically connected dominating set (CDS) partitions and packings are counterparts of edge-disjoint spanning trees, focusing on vertex-disjointness rather than edge-disjointness, and their sizes are always upper bounded by the vertex connectivity k. We constructively show that every k -vertex-connected graph with n nodes has CDS packings and partitions with sizes, respectively, Ω( k /log n ) and Ω( k /log 5 n ), and we prove that the former bound is existentially optimal. Beautiful results by Karger show that when edges of a λedge-connected graph are independently sampled with probability p, the sampled graph has edge connectivity ( λp ). Obtaining such a result for vertex sampling remained open. We illustrate the strength of our approach by proving that when vertices of a k -vertex-connected graph are independently sampled with probability p, the graph induced by the sampled vertices has vertex connectivity ( kp 2 ). This bound is optimal up to poly-log factors and is proven by building an ( kp 2 ) size CDS packing on the sampled vertices while sampling happens. As an additional important application, we show CDS packings to be tightly related to the throughput of routing-based algorithms and use our new toolbox to yield a routing-based broadcast algorithm with optimal throughput Ω( k /log n + 1), improving the (previously best-known) trivial throughput of Θ(1).

Details

STOC Conference 2014 Conference Paper

Are lock-free concurrent algorithms practically wait-free?

  • Dan Alistarh
  • Keren Censor-Hillel
  • Nir Shavit

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free , guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler . Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

Details

STOC Conference 2012 Conference Paper

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance

  • Keren Censor-Hillel
  • Bernhard Haeupler
  • Jonathan A. Kelner
  • Petar Maymounkov

In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the GOSSIP model of communication. In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round. This model contrasts with the much less restrictive LOCAL model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In the LOCAL model, this is quite simple: each node broadcasts all of its information in each round, and the number of rounds required will be equal to the diameter of the underlying communication graph. In the GOSSIP model, each node must independently choose a single neighbor to contact, and the lack of global information makes it difficult to make any sort of principled choice. As such, researchers have focused on the uniform gossip algorithm , in which each node independently selects a neighbor uniformly at random. When the graph is well-connected, this works quite well. In a string of beautiful papers, researchers proved a sequence of successively stronger bounds on the number of rounds required in terms of the conductance φ and graph size n, culminating in a bound of O(φ -1 log n). In this paper, we show that a fairly simple modification of the protocol gives an algorithm that solves the information dissemination problem in at most O(D + polylog (n)) rounds in a network of diameter D, with no dependence on the conductance . This is at most an additive polylogarithmic factor from the trivial lower bound of D, which applies even in the LOCAL model. In fact, we prove that something stronger is true: any algorithm that requires T rounds in the LOCAL model can be simulated in O(T + polylog(n)) rounds in the GOSSIP model. We thus prove that these two models of distributed computation are essentially equivalent.

Details

STOC Conference 2007 Conference Paper

Tight bounds for asynchronous randomized consensus

  • Hagit Attiya
  • Keren Censor-Hillel

A distributed consensus algorithm allows n processes to reach acommon decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in anasynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminatewith probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes.

Details
v2026.09.13