Studia

Data: czwartek, 1 czerwca 2023 r. godz. 12:00

Tytuł: Multiparty communication complexity and additive combinatorics

Miejsce: sala A1-33 (sala Rady naukowej dyscyplin)

Nathan (Nati) Linial jest wybitnym naukowcem pracującym nad zagadnieniami z zakresu matematyki, informatyki, fizyki i biologii. Prowadził badania w wielu czołowych ośrodkach i centrach naukowych takich jak MIT, uniwersytety w Berkeley, Oxfordzie i Cambridge, czy też ośrodki badawcze IBM i Microsoftu. Od 1982 roku jest profesorem na Wydziale Informatyki i Inżynierii w Uniwersytecie Hebrajskim.  Za swoje prace otrzymał wiele wyróżnień i nagród takich jak Nagroda Conanta, przyznana przez Amerykańskie Towarzystwo Matematyczne w 2008 roku, Nagroda Dijsktry, otrzymana w 2013, czy Nagroda Rothschilda, którą został nagrodzony w 2016 roku.

Abstrakt: 

In this talk I only assume familiarity with basic notions from standard mathematical classes, e.g., basic linear algebra. The new material in this lecture was done together with Adi Shraibman. The two mathematical domains in the title of this lecture seem completely disjoint, but I want to convince you that they are actually very closely related. I will discuss the following question in multiparty communication: Three players get together to develop a strategy for the following game. Then they get separated, and a referee writes on their foreheads (previously unknown) integers x, y and z respectively. Now, they get to see each other's foreheads, and their goal is to decide whether x+y=z and do so with the least possible amount of communication. How well can they do?
To illustrate additive combinatorics, take Roth's Theorem: If X is a set of at least n/100 integers between 1 and n, and if n is large enough, then X must contain two integers and their average. The same conclusion holds if 1/100 is replaced by any positive fraction when n is large enough.