Local algorithms with public randomisation on sparse graphs
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 depending only on its constant radius neighbourhood. We show that the information about the local statistics of the graph does not help here at all. Namely, if there exists a local algorithm which can use any local statistics about the graph, and produces a good approximation for a parameter, then there exists an approximation algorithm not using any statistics.