Please note: This PhD defence will take place in DC 2314 and online.
Cameron Seth, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Eric Blais
Graph property testing algorithms aim to distinguish between graphs that have a specific property and graphs that are far from the property by inspecting a small random portion of the graph. A central goal in graph property testing is to determine the minimum size subgraph that must be sampled to test natural graph properties.
This thesis develops a new framework for analyzing graph property testing algorithms using the graph and hypergraph container method. Although the container method has become a powerful tool throughout extremal combinatorics, prior to this work it had not been used to analyze property testing algorithms. We establish a connection between graph property testing and the container method by showing that suitable container lemmas imply strong upper bounds on the sample complexity of canonical property testers for a number of natural properties.
To demonstrate the framework, we develop new graph and hypergraph container lemmas and apply them to three classic property testing problems: testing the property of having a large independent set, testing satisfiability of constraint satisfaction problems, and tolerant testing the property of having a large independent set.
To attend this PhD defence in person, please go to DC 2314. You can also attend virtually on Zoom.