86 citations · 102 across the 13 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DC2012
On the Locality of Some NP-Complete Problems
Leonid Barenboim
We consider the distributed message-passing {LOCAL} model. In this model a communication network is represented by a graph where vertices host processors, and communication is perf…
cs.DC2012★ 86 cited
The Locality of Distributed Symmetry Breaking
Leonid Barenboim, Michael Elkin, Seth Pettie +1
Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this…