Georgia Institute of Technology College of Sciences

The importance of analyzing big data and in particular very large networks has shown that the traditional notion of a fast algorithm, one that runs in polynomial time, is often insufficient. This is where property testing comes in, whose goal is to very quickly distinguish between objects that satisfy a certain property from those that are ε-far from satisfying that property. It turns out to be closely related to major developments in combinatorics, number theory, discrete geometry, and theoretical computer science. 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 permutations, such general results still hold with query complexity only polynomial in 1/ε. We also prove stronger results for graphs through the study of new metrics. These are joint works with Jacob Fox.