Graph Property Testing using the Container Method
| Speaker: | Eric Blais |
| Affilation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: The Graph and Hypergraph Container Methods have recently been used to obtain multiple striking results across different areas of mathematics. In this talk, we will see how the graph container method is particularly well-suited for the study of some fundamental problems in graph property testing.
The main problem we will discuss in the talk is the Independent Set Testing problem introduced by Goldreich, Goldwasser, and Ron (1998). In this problem, we are given oracle access to a graph on $n$ vertices that either (i) contains an independent set on $\rho n$ vertices, or (ii) is $\epsilon$-far from the property in the sense that at least $\epsilon n^2$ edges must be removed from the graph to make it have an independent set of this size. We will introduce a new container lemma for the latter class of graphs and we will show how this lemma can be used to obtain a near-optimal solution to the Independent Set Testing problem. We will also discuss how variants and extensions of the new container lemma can be used to prove a variety of other results in property testing.
This is joint work with Cameron Seth.