Special Computer Science/Discrete Mathematics Seminar Lecture

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 neighborhood. 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. We describe such an algorithm for maximum flow and minimum cut between two disjoint sets of nodes.