Soft-information bounds for monotone-function code ensembles

About 7 years old · traced to

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)=1−H≤dBEC(α,qtBEC),q^{\mathrm{BEC}}_{t+1}(x_0)=1-\mathcal{H}_{\le d}^{\mathrm{BEC}}(\alpha,q^{\mathrm{BEC}}_t),

and

qt+1BSC(x0)=h−1(H≤dBSC(α,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, h−1h^{-1} is the inverse of the binary entropy function on the relevant domain, and o(1)→0o(1)\to0 as k→∞k\to\infty. Soft-information bound conjecture. For a code ensemble generated by a monotone function,

qℓBEC(0)+o(1)≥ιℓBP≥1−hb(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.

References

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.