8 citations · 39 across the 20 of their papers we have counts for
4 papers · 1 filter
Can We Break Symmetry with o(m) Communication?
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju +1
We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in…
The Complexity of Symmetry Breaking in Massive Graphs
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz +1
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related -ruling set problem, in…
Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication
Christian Konrad, Peter Robinson, Viktor Zamaraev
We give lower bounds on the communication complexity of graph problems in the multi-party blackboard model. In this model, the edges of an -vertex input graph are partitioned am…
Network Size Estimation in Small-World Networks under Byzantine Faults
Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson
We study the fundamental problem of counting the number of nodes in a sparse network (of unknown size) under the presence of a large number of Byzantine nodes. We assume the full i…