Data: czwartek, 1 czerwca 2023 r. godz. 12:00
Miejsce: sala A1-33 (sala Rady naukowej dyscyplin)
Prelegent: prof. Nati Linial
Tytuł: Multiparty communication complexity and additive combinatorics
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.
Wideo
Prelegent
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.
Nathan (Nati) Linial is a renowned expert in interdisciplinary research between Mathematics, Computer Science and the Natural Sciences. He has held many visiting positions in international academia and industrial research centers, including MIT, UC Berkeley, Oxford and Cambridge Universities, and long-term appointments at IBM Research and Microsoft Research. Since 1982 he is a Professor at the School of Computer Science and Engineering in the Hebrew University of Jerusalem. For his innovative and novel works he has received a numerous prizes and awards such as the Conant Prize of the American Mathematical Society in 2008, the Dijkstra Prize in Distributed Computing in 2013, and the Rothschild Prize in 2016.
