BLISS Seminar: One-shot Information Theory via Poisson Processes

Seminar | October 30 | 3-4 p.m. | 400 Cory Hall

 Cheuk Ting Li, UC Berkeley

 Electrical Engineering and Computer Sciences (EECS)

In information theory, coding theorems are usually proved in the asymptotic regime where the blocklength tends to infinity. While there are techniques for finite blocklength analysis, they are often more complex than their asymptotic counterparts. In this talk, we study the use of Poisson processes in proving coding theorems, which not only gives sharp one-shot and finite blocklength results, but also gives significantly shorter proofs than conventional asymptotic techniques in some settings. Instead of using fixed-size random codebooks, we construct the codebook as a Poisson process. We present a lemma, called the Poisson matching lemma, which can replace both packing and covering lemmas in proofs based on typicality. We then demonstrate its use in settings such as channel coding with channel state information at the encoder, lossy source coding with side information at the decoder, joint source-channel coding, broadcast channels, and distributed lossy source coding. This shows that the Poisson matching lemma is a viable alternative to typicality for most problems in network information theory.

The talk is based on a joint work with Prof. Venkat Anantharam (UC Berkeley).