Variants of local algorithms on sparse graphs

Understand

Suppose we want to construct some structure on a bounded-degree graph, e.g., an almost maximum matching, and we want to decide about each edge depending only on its constant-radius neighborhood.

• We examine and compare the strengths of different extensions of these local algorithms.
• A common extension is to use preprocessing, which means that we can make some calculation about the whole graph, and each local decision can also depend on this calculation.
• In this paper, we show that preprocessing is needless: if a nearly optimal local algorithm uses preprocessing, then the same can be achieved by a local algorithm without preprocessing, but with a global randomization.