88看球

Organizers：

吴昊，杨帆，姜建平，顾陈琳，李文博

Venue：

C548, Shuangqing Complex Building

Speaker II：

Yanina Shkel (EPFL)

Time：

Thur., 16:30 - 17:20

June 25, 2026

Title：

Minimum Entropy Probability Couplings

Abstract:

The minimum entropy probability coupling problem aims to couple m probability mass functions (PMFs) in a way that minimizes the entropy of the joint PMF. This problem has applications in information theory, causal inference, transportation polytopes, randomness generation, and many more related areas. However, the computation of the minimum entropy coupling is known to be NP-hard. In this talk, we describe a number of known lower bounds on the minimum achievable entropy using tools like majorization and information spectrum. We also discuss several approximation algorithms and their optimality gaps.