On counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)

on YouTube ↗41m

" summary

Shows an algorithm that returns a nearly uniform edge under the vertex/degree/neighbor query model and then makes it exactly uniform, using pointwise closeness rather than TVD, with query cost matching the lower bound O(n/√m). Key tools are heavy–light decomposition (degree threshold ≈ √(m/ε)), rejection sampling on sampled neighbors, and a coin-simulation to fix bias. Works in general graphs, extends to bounded-arboricity cases, and yields optimal, implementable edge samplers for downstream subgraph counting.

AI-written summary · about

" chapters (5)

1. 0:00Introduction
2. 3:45Subgraph counting background
3. 14:40Uniform edge sampling
4. 37:13Exact uniformity via rejection
5. 40:48Closing remarks and Q&A

" related talks

• 01h 02mFine-Grained Counting Complexity IIRadu-Cristian Curticapean · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 01h 02mFine-Grained Counting Complexity IHolger Dell · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 55mSiegel's Theorem, Edge Coloring, and a Holant DichotomyJin-Yi Cai · Tensors in Computer Science and Geometry 2014
• 29mSpotting Trees with Few LeavesŁukasz Kowalik · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 27mSuccinct Preferential Attachment GraphsSebastian Wild · Managing Memory 2025
• 23mWorst-Case to Expander-Case Reductionsamir Abboud, Nathan Wallheimer · ITCS 2023
• 31mNew Unconditional Lower Bounds for Algorithms and Enumeration ProblemsSerge Gaspers · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 34mNew Tools for Peak Memory SchedulingManish Purohit · Managing Memory 2025