Problem index

Channel-capacity problems

Search by channel, method, category, status, or formalization level.

12 entries shown

The initial release is deliberately curated rather than exhaustive.

Channels with memory Updated 2026-08-09

Binary deletion channel

Open Lean: not started

Each input bit is independently deleted without an erasure marker. The exact capacity is unknown for every nontrivial deletion probability.

Point-to-point Updated 2026-08-09

Binary symmetric channel

Solved Lean: definitions

Each bit is independently flipped with probability p. This is the canonical finite noisy channel.

Point-to-point Updated 2026-08-09

Binary erasure channel

Solved Lean: definitions

Each transmitted bit is either received correctly or replaced by a visible erasure symbol.

Point-to-point Updated 2026-08-09

Binary Z-channel

Solved Lean: definitions

One binary symbol is transmitted perfectly while the other can flip in only one direction.

Point-to-point Updated 2026-08-09

q-ary symmetric channel

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.