Binary deletion channel capacity
What is the exact reliable information rate when bits disappear independently and the receiver cannot see where they were removed?
Information and coding
Within Information and coding · Search all subjects
Worst-case trace reconstruction
Do polynomially many independently damaged copies always suffice to recover every unknown binary string exactly?
Shannon capacity of the seven-cycle
Seven symbols sit around a circle, and neighboring symbols can be confused. How many messages can long strings of these symbols carry with absolutely no decoding mistakes?
Binary symmetric channel reliability function
If each transmitted bit flips independently with a fixed probability, adding redundancy reduces mistakes. How quickly can the best possible error probability fall as the message block gets longer?
Li–Li network coding conjecture
Several senders share a network of two-way links. Can mixing their messages inside the network ever carry more independent traffic than forwarding and splitting the messages along paths?