Regularity lemmas are a cornerstone of combinatorics, with many applications in math and CS.  The most famous one is Szemeredi's regularity lemma. It shows that any graph can be partitioned into a "few" parts that mostly "look random". However, there is a caveat - "few" is really a huge number, a tower of exponentials in the error parameter.

Motivated by this, Frieze and Kannan designed a "weak" regularity lemma, sufficient for some applications, where the number of parts is much smaller, only exponential in the error parameter. In this work, we develop an even weaker regularity lemma, called "spread regularity", where the number of parts is even smaller - quasi-polynomial in the error parameter.

I will describe our new notion of regularity and some applications:
1. new lower bound technique in communication complexity, where players partially share information
2. new combinatorial algorithm for boolean matrix multiplication
3. improved bounds for variants of the corners problem in additive combinatorics

Based on joint works with Amir Abboud, Nick Fischer, Michael Jaber, Zander Kelley, Raghu Meka and Anthony Ostuni

 

Short bio: Shachar Lovett is a professor at UC San Diego. He has a broad interest in theoretical CS and combinatorics, with emphasis on structure and randomness, coding theory, algebraic constructions, and additive combinatorics. He is a recipient of an NSF career award, a Sloan fellowship and a Simons investigator award.