![Geometry and Computation in High Dimensions.png](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-05/Geometry%20and%20Computation%20in%20High%20Dimensions.png.jpg?itok=1JtiYLWR)
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.