Jacob Fox
Quantitative Property Testing

Abstract: Over the last couple of decades, it has become abundantly
clear that the analysis of big data is of great importance, and yet
traditional algorithms are too slow to be effective. In recent years,
very general results in property testing have been established which
give "constant time" algorithms for many natural problems. Here, the
running time is independent of the input size, but does depend on a
tolerance parameter. The proof of these results utilize regularity
methods pioneered by Szemeredi, and give tower-type or worse
dependencies on the tolerance parameter, which is useless in
practice. It is therefore a fundamental problem to determine whether
new proofs can be found which give better bounds. In this talk, I will
discuss recent progress on this problem and some closely related major
problems in combinatorics and number theory.