skip to content

Department of Applied Mathematics and Theoretical Physics

Suppose there are (n) parties in a room with a public blackboard that everyone can see. The (i)th party receives an input (X_i), which is not observable by the others. Together, they want to compute a function (f(X_1,\ldots,X_n)). The parties may agree on a protocol in advance, in which they take turns writing bits on the blackboard. If we denote the collection of all bits written on the blackboard by (\Pi), then (f(X_1,\ldots,X_n)) should be computable from (\Pi).


In this work, we study the case where the parties receive i.i.d. samples from either (\operatorname{Ber}(\alpha)) or (\operatorname{Ber}(\beta)), and their goal is to determine which distribution generated the samples. The main question is: what is the minimum amount of information that the parties need to reveal about their inputs in order to perform this task?


We will also see an application of this problem to obtaining a tight lower bound on the communication complexity of multiparty set-disjointness. Finally, we give an application to learning under memory constraints with sparse features.



Further information

Time:

21Oct
Oct 21st 2026
14:00 to 15:00

Venue:

MR5, CMS Pavilion A

Speaker:

Hadi Kazemi, University of Cambridge

Series:

Information Theory Seminar