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.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。