Channels with memory
Updated 2026-08-09
Open
Lean: not started
Each input bit is independently deleted without an erasure marker. The exact capacity is unknown for every nontrivial deletion probability.
\(0.1221(1-d)<C_{\mathrm{del}}(d)\le 0.3578(1-d)\)
Point-to-point
Updated 2026-08-09
Solved
Lean: definitions
Each bit is independently flipped with probability p. This is the canonical finite noisy channel.
\(C_{\mathrm{BSC}}(p)=1-h_2(p)\)
Multi-user
Updated 2026-08-09
Open
Lean: not started
A relay assists communication from a source to a destination. Decode-forward and the cut-set bound do not coincide in general.
\(R_{\mathrm{DF}}\le C\le R_{\mathrm{cut}}\)
Point-to-point
Updated 2026-08-09
Solved
Lean: not started
The power-constrained real Gaussian channel has a closed-form capacity attained by a Gaussian input.
\(C_{\mathrm{AWGN}}(P,N)=\frac12\log_2\!\left(1+\frac{P}{N}\right)\)
Network coding
Updated 2026-08-09
Open
Lean: definitions
This is the smallest multiple-unicast instance identified by Sun and Jafar where Shannon inequalities do not give the best known converse.
\(\frac{5}{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\)
Point-to-point
Updated 2026-08-09
Solved
Lean: definitions
Each transmitted bit is either received correctly or replaced by a visible erasure symbol.
\(C_{\mathrm{BEC}}(\varepsilon)=1-\varepsilon\)
Point-to-point
Updated 2026-08-09
Solved
Lean: definitions
One binary symbol is transmitted perfectly while the other can flip in only one direction.
\(C_Z(p)=\log_2\!\left(1+(1-p)p^{p/(1-p)}\right)\)
Security
Updated 2026-08-09
Solved
Lean: not started
A sender communicates reliably to a legitimate receiver while keeping the message secret from a degraded eavesdropper.
\(C_s=\max_{P_X}\bigl[I(X;Y)-I(X;Z)\bigr]\)
Point-to-point
Updated 2026-08-09
Solved
Lean: definitions
The general finite memoryless point-to-point channel has a single-letter mutual-information characterization.
\(C(W)=\max_{P_X} I(X;Y)\)
Multi-user
Updated 2026-08-09
Solved
Lean: not started
One transmitter sends private messages to two receivers whose outputs form a degradation chain.
\(\mathcal C=\bigcup_{p(u,x)}\{(R_1,R_2):R_1\le I(X;Y_1\mid U),\ R_2\le I(U;Y_2)\}\)
Point-to-point
Updated 2026-08-09
Solved
Lean: not started
The transmitted q-ary symbol is correct with probability 1-p and otherwise changes uniformly to one of the other symbols.
\(C_q(p)=\log_2 q-h_2(p)-p\log_2(q-1)\)
Multi-user
Updated 2026-08-09
Solved
Lean: not started
Two independent senders communicate to one receiver through a memoryless channel, yielding a polymatroidal capacity region.
\(\bigcup_{p(q)p(x_1\mid q)p(x_2\mid q)}\!\left\{\begin{array}{l}R_1\le I(X_1;Y\mid X_2,Q),\\R_2\le I(X_2;Y\mid X_1,Q),\\R_1+R_2\le I(X_1,X_2;Y\mid Q)\end{array}\right\}\)