26 citations · 100 across the 29 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.DS2019
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Yannic Maus, Jara Uitto
The Lovász Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most and d…
cs.DM2019
Navigating an Infinite Space with Unreliable Movements
Anders Martinsson, Jara Uitto
We consider a search problem on a -dimensional infinite grid with a single mobile agent. The goal of the agent is to find her way home, which is located in a grid cell chosen by…
cs.DC2019★ 5 cited
On the Complexity of Distributed Splitting Problems
Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn +2
One of the fundamental open problems in the area of distributed graph algorithms is the question of whether randomization is needed for efficient symmetry breaking. While there are…