Talks
Fall 2020

Counting and Sampling Subgraphs in Sublinear Time
Tuesday, December 15th, 2020, 9:30 am–10:15 am
Speaker:
Talya Eden (MIT)
Location:
Zoom
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.