BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1502
DTSTAMP:20250124T043651Z
SUMMARY:Spread regularity and applications
DESCRIPTION:Speaker: Shachar Lovett (University of California\, San Diego)\
 n\nAbstract: \nRegularity 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.M
 otivated by this\, Frieze and Kannan designed a "weak" regularity lemma\
 , sufficient for some applications\, where the number of parts is much sma
 ller\, only exponential in the error parameter. In this work\, we develop 
 an even weaker regularity lemma\, called "spread regularity"\, where th
 e number of parts is even smaller - quasi-polynomial in the error paramete
 r.I will describe our new notion of regularity and some applications:1. 
 new lower bound technique in communication complexity\, where players part
 ially share information2. new combinatorial algorithm for boolean matrix
  multiplication3. improved bounds for variants of the corners problem in a
 dditive combinatoricsBased on joint works with Amir Abboud\, Nick Fischer
 \, Michael Jaber\, Zander Kelley\, Raghu Meka and Anthony Ostuni\n \nShor
 t bio: Shachar Lovett is a professor at UC San Diego. He has a broad inter
 est in theoretical CS and combinatorics\, with emphasis on structure and r
 andomness\, coding theory\, algebraic constructions\, and additive combina
 torics. He is a recipient of an NSF career award\, a Sloan fellowship and 
 a Simons investigator award.\n
URL:https://www.tcs.tifr.res.in/web/events/1502
DTSTART;TZID=Asia/Kolkata:20250128T093000
DTEND;TZID=Asia/Kolkata:20250128T103000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR