The two-user Gaussian interference channel: a deterministic view

Guy Bresler, David Tse

Introduction: The Challenge of Interference

In the field of multiuser information theory, the two-user Gaussian interference channel (GIC) has long been a central yet elusive problem. It models a scenario where two independent transmitter-receiver pairs attempt to communicate over a shared wireless medium. The fundamental challenge is "interference": Receiver 1's reception of Transmitter 1's signal is corrupted not only by background noise but also by the signal intended for Receiver 2.

Schematic of the two-user Gaussian interference channel with cross-channel gains $h_{12}$ and $h_{21}$.

For over thirty years, the exact "capacity region"—the set of all data rate pairs $(R_1, R_2)$ that both pairs can achieve simultaneously—remained an open problem. While researchers understood the "very strong" interference regime (where the interferer can be decoded and canceled) and the "very weak" regime (where interference is treated as noise), the "moderate" interference regime was poorly understood. Earlier breakthroughs characterized the capacity to within 1 bit, but these results relied on complex "genie-aided" mathematical arguments that lacked physical intuition.

Methods: A Deterministic Lens

To simplify this complexity, the authors introduce a deterministic channel model. This model serves as a high-fidelity proxy by stripping away the probabilistic nature of Gaussian noise and focusing on the interaction of signal levels.

In this framework, signals are viewed as vectors of bits. The "power" of a signal determines its scale—specifically, how many of its bits appear above the noise floor at a given receiver. When multiple signals arrive at a receiver, their bits are added modulo-2 at each level, mimicking physical superposition without the mathematical complexity of integer carries. Noise is modeled simply by truncating any bits that fall below a specific power threshold.

Key Insights: Visualizing Information

The deterministic model provides a powerful "Aha!" moment by making the distinction between common and private information visually clear. Common bits are those received at a high enough power to be seen by both receivers, while private bits are only visible to the intended receiver.

This intuition explains the success of the "Han-Kobayashi" strategy, which involves splitting messages into common and private parts. Furthermore, by analyzing the Generalized Degrees of Freedom (GDOF), the authors show that the deterministic model preserves the essential "shape" of the capacity region in the high-SNR limit.

Key Results: The Constant Gap

The core contribution of the paper is a rigorous proof that the capacity of the Gaussian channel is within a universal constant number of bits of the deterministic model's capacity.

The deterministic model approximates the capacity region within a constant gap, as shown by the proximity of the approximate capacity to the MAC-based outer bounds.

Theorem 1 states that the capacity region of the two-user GIC is within 42 bits per user of the deterministic model's capacity (for complex channels). While 42 bits might seem large in isolation, it is a constant gap. In the high-SNR regime, where total rates can reach thousands of bits, this constant offset becomes negligible. This result provides a much more intuitive derivation of the "constant gap" property than previous methods, offering a clear pipeline for solving complex multiuser problems: convert to deterministic, solve combinatorially, and port the result back with a proven gap.

Limitations and Future Work

Despite its elegance, the approach has limitations. The 42-bit gap is significantly larger than the 1-bit gap found in previous specialized work, as the authors prioritized a simpler, more general argument over numerical optimization. Additionally, while the two-user case is well-handled, extending this deterministic framework to $N$-user networks or complex relay topologies remains a significant theoretical challenge. Future work will focus on tightening these bounds and scaling the model to more complex network architectures.

Summary updated

BibTeX
@article{bresler2008two,
  author = {Guy Bresler and David Tse},
  title = {{The two-user Gaussian interference channel: a deterministic view}},
  journal = {Eur. Trans. Telecommun.},
  year = {2008},
  doi = {10.1002/ett.1287},
}
Figure