Property Testing for Graphs

on YouTube ↗01h 23m

" summary

Survey of graph property testing that draws a sharp line between models and gives concrete bounds: dense graphs admit constant‑query testers for every hereditary property by using the Szemerédi regularity lemma (but with tower‑type dependence; Fox reduces triangle removal to a tower of log(1/ε)), bounded‑degree graphs test connectivity by sampling plus local BFS in constant time while bipartiteness needs about √n queries via many short random walks, and directed/unbounded‑degree models remain largely open.

AI-written summary · about

" chapters (8)

1. 0:00Program introduction
2. 3:24Overview of program themes
3. 6:35Introduction to property testing
4. 17:13Adjacency matrix model
5. 22:59Algorithms and complexity
6. 43:20Adjacency list model
7. 1:01:46General graphs and models
8. 1:12:20Discussion and Q&A

" related talks

• 23mTowards General and Tight Hardness Results for Graph ProblemsChristian Komusiewicz · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 01h 37mGraphons and Graph Limits 3Jennifer Chayes · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 01h 31mGraphons and Graph Limits 2Christian Borgs · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 01h 07mMarrying Graph Convergence and Cascade ModelsYeganeh Ali Mohammadi · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 35mSuperlinear Lower Bounds for Multipass Graph ProcessingKrzysztof Onak · Information Theory in Complexity Theory and Combinatorics 2015
• 59mHardness for Graph Problems - Reductions Based on APSP and SETHVirginia Vassilevska Williams · Fine-Grained Complexity and Algorithm Design Boot Camp 2015
• 23mA New Connection Between Node and Edge Depth Robust GraphsJeremiah Blocki, Mike Cinkoske · ITCS 2021
• 50mVerifying a distributed system with combinatorial topologyVeronica Lopez · Code Mesh LDN 2018