Abstract

Over the past decade, there have been a number of results of estimating subgraph counts without reading the whole graph. The aim of this talk is to bring out some key randomization techniques used in these results. These tools are simple enough to explain in a few slides, yet powerful enough to prove optimal results for estimating the average degree and triangle count. The hope is that the audience can understand all the details enough to recreate the results.

Attachment

Video Recording