Talks
Fall 2020

# Counting and Sampling Subgraphs in Sublinear Time

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

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.