Submit progress

on Constant term of one-shot channel simulation ($C_{32}$)

The statement

The constant term of one-shot channel simulation [HJMR07], [BG14], [LEG18], [Li25] is given as (we use the definition in [Li25])

C_{32}=\mathrm{limsup}_{t\to\infty}(\sup_{p_{X,Y}: I(X;Y)=t} \inf_{p_{S|X,Y}: I(X;S)=0}H(Y|S)-t-\log_{2}t),

where $H(Y\lvert S)=H(Y,S)-H(S)$ is the conditional entropy (in bits), and $I(X;Y)=H(X)+H(Y)-H(X,Y)$ is the mutual information (in bits). The supremum and infimum are over arbitrary finite discrete joint probability distributions $p_{X,Y}$ with $I(X;Y)=t$ and finite discrete conditional distributions $p_{S\lvert X,Y}$ with $I(X;S)=0$ , respectively.

Equivalently, it is the smallest (i.e., infimum of) $\alpha\in\mathbb{R}$ satisfying that there exists $\beta>0$ such that for every jointly-distributed random variables $X,Y$ with finite support, we can construct a random variable $S$ with finite support (jointly-distributed with $X,Y$ , possibly after extending the probability space) with $I(X;S)=0$ and $H(Y\lvert S)\le I(X;Y)+\log_{2}(I(X;Y)+\beta)+\alpha$ [LEG18], [Li25].

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.