Fast Testing of Graph Properties
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19
summary
Characterizes what's testable fast and where costs hide: dense graphs (adjacency matrix) admit constant-query testers for all hereditary properties but with tower-type dependence on ε (Alon–Shapira), while sparse bounded-degree graphs use random sampling, local BFS and √n random walks of length O(log n) to test bipartiteness and acyclicity (Goldreich–Ron upper and √n lower bound); 3-colorability needs linear time (Bogdanov–Matoušek–Trevisan), planarity is constant-time two-sided via hyperfiniteness, and unbounded-degree lists remain largely open.
AI-written summary · about
chapters (20)
- 0:00Intro
- 0:39Fast Testing of Graph Properties (in Big Data setting)
- 2:20Framework of property testing
- 3:06Property Testing definition
- 5:22First model: Adjacency Matrix
- 10:10General result
- 10:41Main Lemma
- 14:23Problems of adjacency matrix model
- 15:27Second model: Adjacency Lists
- 17:02Bounded-degree adjacency list model
- 23:07Testing cycle-freeness in bounded-degree graphs one-sided error
- 30:44Extension: all minor-closed properties
- 30:57Testing expansion
- 33:56Testing in planar graphs
- 34:28Testing in hyperfinite graphs
- 36:37Adjacency Lists in arbitrary graphs
- 37:09Testing in arbitrary graphs
- 37:30Testing in arbitrary planar graphs
- 38:02Extensions
- 38:19Summary