The day after tomorrow:

[Alexander Shen]

(Information theory seminar - wholeheartedly recommended!)

Dear colleagues,

The next meeting of our seminar is planned for Wednesday, April 10, at
17h of summer Paris time, https://time.is/CEST. Our speaker is Alexander
Kozachinskiy (Catholic University of Chile), who will talk about
"Information-theoretic methods in communication complexity."

We will discuss the roots of information-theoretic techniques that are
nowadays very popular in communication complexity. This talk is *not*
intended for communication complexity experts.

Abstract:  Imagine that Alice and Bob both hold a binary string of
length n, and they want to know if there is a position, where both their
strings have 1. This problem is called Disjointness. A fundamental
result in communication complexity states that even if Alice and Bob
have access to randomness and are allowed to error with small
probability, they need to send each other Omega(n) bits to solve
Disjointness. In the talk, I will present an information complexity
proof technique that was developed by different authors in the 2000s and
by now has become classical. This method, in the nutshell, uses the
chain rule for mutual information to formalize an intuition that we
cannot do better in solving Disjointness than checking individually all
n positions.


Zoom session:
https://cnrs.zoom.us/j/92698837672?pwd=R3BKNVFBK2JqYzJsRWxQaDluM0NDQT09

Meeting ID: 926 9883 7672
Passcode: Kq3EVs


Best regards,
Andrei