← All problems

Capacity of the Binary Deletion Channel

Determine the exact average-error Shannon capacity C_del(d), in bits per input bit, of the binary deletion channel for every real d with 0<d<1. Each input bit is independently deleted with probability d; surviving bits retain their order, and neither terminal observes the deletion pattern.

Source: Cheraghchi and Ribeiro, An Overview of Capacity Results for Synchronization Channels.

Status Open Open. The September 2026 primary preprint explicitly records that exact capacity is unknown and offers a uniform numerical approximation; this is partial progress, not an exact-function resolution. Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.

References

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.