Information-theoretic methods in communication complexity.

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.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.