Explore key randomization techniques for estimating subgraph counts without reading entire graphs in this 1-hour lecture by C. Seshadhri from UC Santa Cruz. Delve into simple yet powerful tools that yield optimal results for estimating average degree and triangle count. Gain a thorough understanding of the details, enabling you to recreate these results independently. Part of the Sublinear Algorithms Boot Camp at the Simons Institute, this talk offers insights into a decade of advancements in sublinear graph algorithms.
Overview
Syllabus
Counting Subgraphs in Sublinear Time
Taught by
Simons Institute
Related Courses
-
Sublinear Time Algorithms for Estimating Edit Distance
-
Graph Coloring Through the Sublinear Lens
-
Linear and Sublinear Algorithms for Graphlet Sampling
-
Recent Progress on Sublinear Time Algorithms for Maximum Matching - Upper Bounds
-
Sublinear-Time Algorithms in Learning
-
Sublinear Time Algorithms for Max-Cut Approximation on Expander Graphs
