We typically have seminars on Wednesday at noon in Malone 228. All seminar announcements will be sent to the theory mailing list.
Speaker: Marius Zimand
Affiliation: Towson University
Title: An operational characterization of mutual information in algorithmic information theory
Abstract: An operational interpretation of the concept of mutual information in the framework of Kolmogorov complexity has been elusive till now. We show that the mutual information of any pair of strings x and y is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having x and the complexity profile of the pair and the other one having y and the complexity profile of the pair, can establish via a probabilistic protocol with interaction on a public channel. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length, for protocols with public randomness. We show that if the communication complexity drops below the established threshold then only very short secret keys can be obtained.
This is joint work with Andrei Romashchenko.
Speaker: Yasamin Nazari
Speaker: Karthik Abinav Sankararaman
Affiliation: University of Maryland
Speaker: Jalaj Upadhyay