Seminar

We typically have seminars on Wednesday at noon in Malone 228.  All seminar announcements will be sent to the theory mailing list.

Oct
3
Wed
[Theory Seminar] Marius Zimand
Oct 3 @ 12:00 pm – 1:00 pm

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.

Oct
10
Wed
[Theory Seminar] Yasamin Nazari
Oct 10 @ 12:00 pm – 1:00 pm

Speaker: Yasamin Nazari
Affiliation: JHU

Title: TBA

Abstract: TBA

Oct
17
Wed
[Theory Seminar] Karthik Abinav Sankararaman @ Malone 228
Oct 17 @ 12:00 pm – 1:00 pm

Speaker: Karthik Abinav Sankararaman
Affiliation: University of Maryland

Title: TBA

Abstract: TBA

Nov
7
Wed
[Theory Seminar] Jalaj Upadhyay
Nov 7 @ 12:00 pm – 1:00 pm

Speaker: Jalaj Upadhyay
Affiliation: JHU

Title: TBA

Abstract: TBA

Nov
16
Fri
Capital Area Theory Day @ Georgetown University
Nov 16 all-day
Feb
13
Wed
[Theory Seminar] Martin Farach-Colton
Feb 13 @ 12:00 pm – 1:00 pm

Speaker: Martin Farach-Colton
Affiliation: Rutgers University

Title: TBA

Abstract: TBA