Soft-information bounds for monotone-function code ensembles

Let α=C/R\alpha=C/R, and let qtBECq^{\mathrm{BEC}}_t and qtBSCq^{\mathrm{BSC}}_t be the dynamical systems initialized at x0x_0 by

qt+1BEC(x0)=1HdBEC(α,qtBEC),q^{\mathrm{BEC}}_{t+1}(x_0)=1-\mathcal{H}_{\le d}^{\mathrm{BEC}}(\alpha,q^{\mathrm{BEC}}_t),

and

qt+1BSC(x0)=h1(HdBSC(α,qtBEC)).q^{\mathrm{BSC}}_{t+1}(x_0)=h^{-1}(\mathcal{H}_{\le d}^{\mathrm{BSC}}(\alpha,q^{\mathrm{BEC}}_t)).

Here ιBP\iota^{\mathrm{BP}}_\ell is the soft information output after \ell iterations of belief propagation, h1h^{-1} is the inverse of the binary entropy function on the relevant domain, and o(1)0o(1)\to0 as kk\to\infty. Soft-information bound conjecture. For a code ensemble generated by a monotone function,

qBEC(0)+o(1)ιBP1hb(qtBSC(1/2))+o(1).q^{\mathrm{BEC}}_\ell(0)+o(1)\ge \iota^{\mathrm{BP}}_\ell\ge 1-h_b\bigl(q^{\mathrm{BSC}}_t(1/2)\bigr)+o(1).

The source presents this as a conjectured bound for majority codes, or perhaps more generally for binary monotone functions. Since the supplied parser status is unknown, its resolution is not established here.

Sources & referencesView supporting material

Primary source

Hajir Roozbehani and Yury Polyanskiy, “Low density majority codes and the problem of graceful degradation”, arXiv:1911.12263 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.