Fall 2020

Counting and Sampling Subgraphs in Sublinear Time

Tuesday, December 15th, 2020 9:30 am10:15 am

Add to Calendar


Talya Eden (MIT)

In this talk I will shortly survey recent developments in approximate subgraph counting and sampling in sublinear-time. Both counting and sampling small subgraphs is a basic primitive, well studied both in theory and in practice. We consider these problems in the sublinear-time setting, where access to the graph $G$ is given via queries. We will consider both general graphs, and graphs of bounded arboricity which can be viewed as ``sparse everywhere" graphs, and we will see how we can use this property to obtain substantially faster algorithms.