slideshow 3

Fan Wei (Stanford): Permutation Property Testing

Fan Wei

Stanford Unversity
10/05/2019 - 10:00 to 11:30
Modra poslucharna
Fast Permutation Property Testing

Szemerédi's regularity lemma is an important and powerful tool in graph theory. Although the regularity lemma is powerful, a notable drawback is that applications of the regularity lemma will result in very weak quantitative estimates. One important application of the regularity lemma is the field of property testing, whose goal is to very quickly distinguish between objects that stratify a certain property from those that are ε-far from satisfying that property. Some of the most general results in this area give "constant query complexity" algorithms, which means the amount of information it looks at is independent of the input size. These results are proved using regularity lemmas or graph limits. Unfortunately, typically the proofs come with no explicit bound for the query complexity, or enormous bounds, of tower-type or worse, as a function of 1/ε, making them impractical. We show by entirely new methods that for testing hereditary permutations properties, such general results still hold with query complexity only polynomial in 1/ε.
This is a joint work with Jacob Fox.
More information about the combinatorics seminar: