Combinatorics: Adi Shraibman (MTA)

Mon, 05/04/202110:00-12:00
Sprinzak Building, Jerusalem, Israel

HUJI Combinatorics Seminar 

When: Monday April 5, 2021, at 10AM

Where: Sprinzak 28

Speaker: Adi Shraibman (MTA)
Title: Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols

A subset of the integer planar grid [N]x[N] is called corner-freeif it contains no triple of the form (x,y), (x+d,y), (x,y+d). It is known that
such a set has a vanishingly small density, but how large this density can be remains unknown.
The best previous construction was based on Behrend's large subset of [N] with no 3-term arithmetic progression.
Here we provide the first substantial improvement to this lower bound in decades. 
Our approach to the problem is based on the theory of communication complexity.

Joint work with Nati Linial.