Counting and Sampling Subgraphs in Sublinear Time

          @misc{ scivideos_16864,
            doi = {},
            url = {https://simons.berkeley.edu/talks/counting-and-sampling-subgraphs-sublinear-time},
            author = {},
            keywords = {},
            language = {en},
            title = {Counting and Sampling Subgraphs in Sublinear Time},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {dec},
            note = {16864 see, \url{https://scivideos.org/Simons-Institute/16864}}
          }
          

Abstract

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.