Extremal rate and mutual-information regions of binary channels
Follow the latest progress by email.
For a doubly symmetric binary source of crossover p∈[0,1], do arbitrary binary channels and binary symmetric channels generate the same convex hull of rate triples? At p=0, related questions ask whether prescribed Z/S and Z/Z channel pairs extremize I(U;V) under their respective rate constraints, for a,d∈(0,1).
Why it matters and what counts as progress
Why it matters: The questions ask whether simpler symmetric channels capture an entire rate region and whether asymmetric channels attain constrained information extrema.
What counts as progress: Prove the convex-hull equality or either constrained value bound across its full parameter range; equality of values does not imply uniqueness of optimizers.
How the problem developed
- 19 Sept 2022 · Conjectures [1]
Michael Dikshtein, Or Ordentlich and Shlomo Shamai Published two double-sided information-bottleneck conjectures for the identical-source case, predicting binary-channel pairs that attain the maximum and minimum mutual information at fixed rates.
Georg Pichler; substantial AI assistance is acknowledged Proved the averaged-BSC conjecture for every crossover p and both double-sided bottleneck conjectures for binary outputs, with Z/S-channel extremizers.
AI contribution
Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source
For a doubly symmetric binary source with crossover p∈[0,1], the convex hull of rate triples from arbitrary binary channels equals that from binary symmetric channels. At p=0 and parameters a,d∈(0,1), no binary channel pair with rates no larger than the stated Z/S pair has greater I(U;V), and no pair with rates at least those of the stated Z/Z pair has smaller I(U;V). These are value bounds, not uniqueness claims.
Sources
Website timeline
Publication dates and editorial changes.