Random local algorithms
Endre Csóka · arXiv (Cornell University) · 2012
Consider the problem when 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 de-pending only on its constant radius neighbourhood. We show that the information about the local statistics of the graph does not help here. Namely, if there exists a random local algorithm which can use any local statistics about the graph, and produces an almost optimal structure, then the same can be achieved by a random local algorithm using no statistics.