Title: Optimization in very large graphs

Abstract:

Algorithmic questions concerning very large graphs present novel challanges, and
some of the classical algorithmic problems must be rephrased and a new kind of
complexity theory emerges. By "very large" we mean a graph whose nodes and edges are
too numerous to be treated as a single file of data, and often even the number of
nodes is not known. We assume that information about such graphs is obtained by an
appropriate sampling procedure.

It is clear that every computational result will only be approximate, but this is
not the only problem. What should it mean to compute a perfect matching or a maximum
cut in such a graph? One possible approach is to give an algorithm that computes the
answer locally, from the sampling data. Making this precise connects optimization with
techniques in graph theory developed to handle large graphs (like regularity
partitions and graph limits).