Please note: This PhD seminar will take place in DC 1304.
Cameron Seth, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Eric Blais
Recent results have shown that the graph container method is a useful tool for analyzing property testing algorithms for a number of classic properties including $k$-colorability, $\rho$-clique and satisfiability. In this talk we will demonstrate that there is a deeper connection between the container method and graph property testing. For hereditary properties, we relate one-sided testability to the existence of a type of container lemma, and we obtain quantitative bounds in both directions. As applications, we obtain closure results for partition properties and new testing results for graph and digraph properties such as the dichromatic number.