BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1343
DTSTAMP:20231109T045017Z
SUMMARY:Improved constructions of large-dimensional corner-free sets
DESCRIPTION:Speaker: Suhail Sherif (LASIGE\, University of Lisbon)\n\nAbstr
 act: \nIn this talk we will discuss some famous open problems in additive 
 combinatorics:- How large can a subset S of [N] be while managing to avoid
  k-term arithmetic progressions?- How large can a subset S of [N]^k be whi
 le managing to avoid a k-dimensional corner? (If ⋯ represents a 3-term a
 rithmetic progression\, then ⠓ represents a 2-dimensional corner. A more
  formal definition will be provided in the talk\, or can be found in the p
 aper linked below.)We will also discuss multiparty communication complexit
 y\, wherein players are given inputs and they want to compute a function o
 f those inputs. In the Number-In-Hand model\, each player can see their ow
 n input but not the inputs of others. In the Number-On-Forehead model\, ea
 ch player can see the other players' inputs but not their own.In 2021 Lini
 al and Shraibman utilized a long-known connection which showed that findin
 g good k-party Number-On-Forehead communication protocols for the "Exactly
 N" function is equivalent to finding large (k-1)-dimensional-corner-free s
 ets. Working in the setting when k=3\, they constructed an explicit protoc
 ol that matched a 1946 construction of large corner-free sets. Using the c
 ommunication complexity point of view\, they improved upon the protocol to
  create even larger sets\, giving the first improvement to the "highest-or
 der" term since 1946. This was then subsequently improved by Green later t
 hat year.In our work we generalize this method to larger dimensions. We cr
 eate explicit communication protocols that match a 1961 construction of la
 rge k-dimensional-corner-free sets. We then provide an improvement in the 
 same vein as Linial and Shraibman and Green\, giving the first improvement
  to the "highest-order" term since 1961.This is joint work with Lianna Ham
 bardzumyan\, Toniann Pitassi\, Morgan Shirley and Adi Shraibman. The paper
  can be found at https://arxiv.org/abs/2309.06554.\n
URL:https://www.tcs.tifr.res.in/web/events/1343
DTSTART;TZID=Asia/Kolkata:20231114T160000
DTEND;TZID=Asia/Kolkata:20231114T173000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR