Endre Csóka: A simple proof of entropy and correlation inequalities of local algorithms on graphs

Speaker: Endre Csóka

Title: A simple proof of entropy and correlation inequalities of local algorithms on graphs

Abstract: Local algorithms on graphs (essentially the same as factor of iid processes) are constant-time randomized distributed algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph, e.g. a large independent set. The aim of the research is to characterize what can be computed by local algorithms. There are some nontrivial necessary conditions, for example, we cannot construct an almost proper two-coloring of the vertices in any large-girth d≥3 -regular graph. General entropy inequalities and correlation inequalities were proved about the output of local algorithms in several papers by Ágnes Backhausz, Balázs Szegedy and others, using difficult techniques. We show a simple idea which proves all of these inequalities with some new entropy inequalities.