Information theory is a branch of applied mathematics, electrical engineering, and computer science that involves the quantification, storage, and communication of information. Since its inception by Claude Shannon in 1948, several fundamental problems have remained unsolved or only partially resolved. These problems typically involve characterizing the fundamental limits of communication systems.
1. Capacity of the General Relay Channel
The relay channel, first introduced by van der Meulen in 1971, involves a source, a destination, and a relay node that assists the transmission. While the capacity is known for specific cases—such as the degraded relay channel—the capacity formula for the general relay channel remains an open problem. Researchers have established inner bounds (achievable rates) and outer bounds (theoretical limits), but these bounds do not meet in the general case.
2. Capacity of the Interference Channel
The interference channel describes a scenario where multiple transmitter-receiver pairs communicate over a shared medium, creating mutual interference. Characterizing the exact capacity region for a general two-user interference channel is a long-standing challenge. Although the capacity for the "strong interference" case is known and the "one-bit-to-capacity" approximation for the Gaussian interference channel was achieved in 2008, a general solution for all channel parameters has not been determined.
3. Shannon Capacity of Graphs
In zero-error information theory, the Shannon capacity of a graph represents the maximum rate at which information can be sent across a channel such that no errors occur. For many graphs, this value is unknown. While Lovász famously determined the capacity of the five-cycle graph ($C_5$) in 1979, the Shannon capacity for the seven-cycle graph ($C_7$) and most larger odd cycles remains unsolved.
4. Distributed Source Coding with Distortion
The Slepian-Wolf theorem characterizes the lossless compression of correlated sources. However, the lossy version of this problem—determining the rate-distortion region for multiple correlated sources (distributed source coding)—is only partially solved. The general rate-distortion region for two or more sources under various distortion constraints (the "CEO problem" being one specific variant) remains an active area of research with many unresolved cases.
5. Network Coding for Non-Multicast Sessions
In network coding, it is known that for multicast sessions (one source to many destinations), the max-flow min-cut theorem determines the capacity. However, for non-multicast sessions—such as multiple-unicast sessions where different sources send information to different destinations—finding the necessary and sufficient conditions for a given rate vector to be achievable is an open problem. It has been proven that linear network coding is insufficient for general networks, complicating the search for a universal solution.
6. Capacity of Channels with Feedback
While Shannon proved that feedback does not increase the capacity of a memoryless point-to-point channel, it can increase the capacity of channels with memory or multi-user channels. Characterizing the exact capacity gain and the optimal coding strategies for general channels with feedback (especially non-Gaussian channels with memory) is an ongoing challenge in the field.
7. Quantum Information Theory Open Problems
In the extension of information theory to quantum systems, several problems remain, including the additivity of certain channel capacities. Although some conjectures regarding the additivity of the Holevo capacity were disproven by counterexamples, many questions regarding the exact capacity of quantum channels for transmitting classical or quantum information remain open.
