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
-
Subgraph Counting and Seed Counting in Graph Theory
-
Sublinear Time Algorithms for Estimating Edit Distance
-
Linear and Sublinear Algorithms for Graphlet Sampling
-
Sublinear Algorithms in Social Networks via Core-Periphery Decomposition
-
Recent Progress on Sublinear Time Algorithms for Maximum Matching - Upper Bounds
-
Sublinear-Time Algorithms in Learning
