比利时vs摩洛哥足彩
,
university of california san diego
****************************
math 269: seminar in combinatorics
prof. shachar lovett
uc san diego (slovett@cs.ucsd.edu)
spread regularity and applications
abstract:
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
lutz warnke
november 19, 2024
2:00 pm
apm 7321
research areas
combinatorics****************************