Gábor Elek: Learning Very Large Graphs with Unknows Vertex Distributions

Speaker: Gábor Elek

Title: Learning Very Large Graphs with Unknows Vertex Distributions

Abstract: Recently, Goldreich introduced the notion of property testing of bounded-degree graphs with an unknown distribution. We propose a slight modification of his idea: the Radon-Nikodym Oracles. Using these oracles any reasonable graph property can be tested in constant-time against any reasonable unknown distribution in the category of planar graphs. We also discuss Randomized Local Distributed Algorithms, which work on very large graphs with unknown distributions. Finally, we discuss how can we learn graph properties using observations instead of samplings.