סוג האירוע

בחר הכל

הרצאות פומביות

קולוקוויום

סמינרים

כנסים וימי עיון

מועדון IAP

The Story of Multi-Party Set Disjointness

Prof. Rotem Oshman

13 ביוני 2021, 11:00 
Seminar room 420, fourth floor, Check Point Building.  
קולוקוויום במדעי המחשב

Abstract

 

Communication complexity studies the amount of communication that two or more parties must exchange in order to compute a function whose input is initially partitioned between the parties

One central problem in the field, the two-party set disjointness problem, has attracted significant attention due to its many applications in areas of theoretical computer science: in two-party set disjointness, each player receives a subset of the elements {1,...,n}, and the goal is to determine whether the intersection of the players' subsets is empty or not. Razborov famously showed that solving set disjointness requires Omega(n) bits of communication between the two parties

In this talk I will describe recent results on the multi-party version of set disjointness, where we have k > 2 parties

I will focus on two results that show how multi-party set disjointness differs from two-party disjointness: first, multi-party set disjointness is sensitive to the amount of interaction that the parties are allowed to have with one another (and this result has an application to the communication cost of welfare-maximization with limited interaction). Second, if k > log(n), we can show that even when we work with relatively "simple" distributions, where the players' inputs are independent of one another, the problem still requires Omega(n) communication, making it almost as hard as the non-product case.

 

This is joint work with Mark Braverman, Nachum Dershowitz, and Tal Roth. No prior knowledge on communication complexity will be assumed for the talk

Where: Seminar room 420, fourth floor, Check Point Building

or via Zoom link: https://us02web.zoom.us/j/83215079523?pwd=TjBTdk9OZHQxRlJGdDlxTno4NGJKZz09

 

אוניברסיטת תל אביב עושה כל מאמץ לכבד זכויות יוצרים. אם בבעלותך זכויות יוצרים בתכנים שנמצאים פה ו/או השימוש
שנעשה בתכנים אלה לדעתך מפר זכויות, נא לפנות בהקדם לכתובת שכאן >>