The regularity lemmas is a game-changer in extremal combinatorics, and has connection to number theory, discrete geometry, and theoretical computer science. One of its classical applications, the removal lemmas, are a building block for many property testing problems. Unfortunately, typically the proofs come with no explicit bound for the query complexity, or enormous bounds, making them impractical. We show for testing hereditary permutation properties, a different partition yields a tester with a polynomial in 1/ε query complexity . For graphs, we prove a stronger version of the graph removal lemma, where we conjecture that the essence of this new removal lemma is the regularity-type proof, and thus should yield enormous bounds. 

A second topic in the talk is around a fundamental question about probabilistic methods:  when is randomness nearly optimal? Here we developed a method, using graph limits and combining both analytic and spectral methods,  to tackle some old open questions, and also make advances towards some other famous conjectures on graph homomorphism density inequalities. 

These works are based on joint works with Fox, Kral', Noel, and Volec.