Endre Csoka
Local algorithms on random graphs and on graph limits
Abstract: Sparse graph limit theory aims to understand how do local
properties of large graphs with bounded degrees determine global
properties of the graph. For a version of this question, the answer is
possibly that only through local algorithms. We will give an overview
about the relation between local algorithms, graphs limits and large
random graphs, and we will sketch our current knowledge about the
exact power of local algorithms, including some very recent entropic
bounds.