A living research index

Know the channel. See the gap. Work on the proof.

A community-maintained atlas of channel capacities, open gaps, and Lean formalizations.

Every entry separates literature claims from machine-checked Lean proofs.

Open capacity gap
\[\frac{5}{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\]
Achievability open Converse
Sun-Jafar 11-message instance
12capacity problems
3open problems
9solved entries
5Lean work started
Featured problems

Start from a precise research target

Each page fixes the model, rate convention, best bounds, provenance, and what would count as progress.

View all 12 problems
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.

\(0.1221(1-d)<C_{\mathrm{del}}(d)\le 0.3578(1-d)\)
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.

\(C_{\mathrm{BSC}}(p)=1-h_2(p)\)
Multi-user Updated 2026-08-09

General discrete memoryless relay channel

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

Real additive white Gaussian noise channel

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)\)
Built for research

More than a table of formulas

01

Exact specification

Inputs, outputs, transition law, side information, constraints, error criterion, and normalization are explicit.

02

Bounds as data

Every achievability and converse has its own method, conditions, year, and references.

03

Research frontier

Open entries explain the bottleneck and list concrete results that would move the state of the art.

04

Lean, honestly labelled

Definitions, statements, partial proofs, and complete proofs are distinct statuses. No badge hides a missing theorem.

Formalization policy

Lean is the only proof-assistant target for now

Channel definitions live in shared modules. Contributions should reuse those definitions, contain no sorry, and name the exact theorem that has been checked.

See the Lean dashboard
  1. 1
    DefinitionsThe model compiles.
  2. 2
    StatementThe capacity claim is stated precisely.
  3. 3
    PartialSome bounds or lemmas are proved.
  4. 4
    CompleteThe claimed result is machine-checked.