Constant Gap Capacity Approximation

55 concepts48 papers1 proposal

For decades, finding the exact capacity of multi-user wireless networks was considered an intractable problem. While Claude Shannon elegantly solved the point-to-point channel capacity in 1948, adding even a single interfering user or a relay node introduces complex multi-dimensional optimization problems.

To bypass this mathematical bottleneck, researchers shifted their focus from finding exact capacity formulas to finding approximate capacity characterizations. The core idea is simple yet powerful: design transmission strategies where the gap between the achievable rate and the absolute theoretical limit is bounded by a universal constant—independent of the signal-to-noise ratio (SNR) and channel gains.

Moving Beyond Degrees of Freedom

Traditionally, information theorists used "Degrees of Freedom" (DoF) to characterize high-SNR behavior. DoF measures the slope of the capacity curve as power goes to infinity, essentially treating capacity as:

$$\text{Capacity} \approx \text{DoF} \cdot \log(\text{SNR}) + o(\log(\text{SNR}))$$

However, as Sang-Woon Jeon points out in Approximate Ergodic Capacity of a Class of Fading 2-user 2-hop Networks, a DoF characterization only ensures that the approximation error is small relative to the total rate. This allows the absolute gap in bits to grow infinitely as SNR increases.

In contrast, a constant-gap capacity approximation guarantees that:

$$\text{Capacity} - \text{Achievable Rate} \le \text{Constant}$$

This means that whether your transmitter is operating at a few milliwatts or megawatts, the practical transmission strategy remains within a predictable, small number of bits from the absolute physical limit.

The One-Bit Breakthrough

The foundational breakthrough of this paradigm came from Etkin et al. in their study of the two-user Gaussian interference channel, Gaussian Interference Channel Capacity to Within One Bit: the General Case.

Instead of trying to perfectly coordinate the users, the authors proposed a simple message-splitting strategy. Each user divides their message into two parts:

  1. A Public Message: Transmitted with enough power to be decoded by both the intended receiver and the interfering receiver. Once decoded by the unintended receiver, it can be subtracted to eliminate interference.
  2. A Private Message: Transmitted at a lower power level so that it can only be decoded by the intended receiver.

The key intuition introduced by Etkin et al. is a simple rule of thumb: set the power of the private message such that its interference arrives at the unintended receiver exactly at or below the background noise level.

[Transmitter 1] ----(High Power Public + Low Power Private)----> [Receiver 1]
                       \
                        \ (Private part drops below noise floor)
                         v
                       [Receiver 2]

By doing this, the unintended receiver can simply treat the remaining private interference as background noise without losing significant capacity. The authors proved that this intuitive strategy achieves a transmission rate within exactly one bit per second per Hz of the true theoretical capacity, universally across all channel parameters.

Extending the Paradigm to Feedback and Relays

This "constant-gap" philosophy quickly expanded to more complex network topologies and features, proving that complex coordination strategies often boil down to simple geometric bounds.

Feedback Channels

In point-to-point channels, feedback does not increase capacity. However, in interference channels, feedback allows transmitters to adapt to what the other user received. Suh et al. demonstrated in Feedback Capacity of the Gaussian Interference Channel to within 2 Bits that a strategy leveraging feedback can bound the capacity region to within 1–2 bits per user across all signal and interference levels, proving that feedback provides massive, multiplicative gains rather than just additive ones.

Relay Networks

For networks where intermediate nodes assist in forwarding data, Avestimehr et al. showed in Approximate capacity of Gaussian relay networks that a relaying strategy can achieve data rates within a fixed number of bits from the theoretical capacity, completely independent of channel strengths or SNR. This shifted the focus of network design away from exact power allocation toward routing and stream alignment.

Why Does It Work? The Intuition of Outer Bounds

Why can we bound these complex, continuous Gaussian channels so tightly? The secret lies in a two-step methodology that bridges discrete mathematics and continuous physics.

First, researchers often solve a simplified, noise-free "linear deterministic" version of the network, where signals are represented as binary vectors and channel gains act as bit-shifts. This isolates the combinatorial structure of how signals overlap and interfere.

Second, to prove the gap is constant, the inner bounds (achievable rates) must be matched against tight outer bounds (converse proofs). While the classic cut-set bound is a standard tool in information theory, it is often too loose. To tighten the gap, researchers develop "genie-aided" bounds, where an imaginary genie gives clever side-information to certain receivers to simplify the network dependencies.

For example:

When the mathematical expressions for these tighter outer bounds are subtracted from the achievable inner bounds, the signal power terms ($\log(\text{SNR})$) cancel out completely. What remains is a residual gap that depends only on the physical topology of the network—such as the number of antennas in a MIMO system, which Ashraphijuo et al. showed determines the constant gap in On the Capacity and Degrees of Freedom Regions of Two-User MIMO Interference Channels With Limited Receiver Cooperation.

Ultimately, constant-gap capacity approximation works because it proves that the chaotic, continuous nature of wireless interference can be tamed. By focusing on the structural bottleneck of a network rather than fine-tuning for noise, simple strategies like rate-splitting and lattice codes can capture nearly all the capacity a channel has to offer.

Key Foundational Work

Cooperative relay broadcast channels (2005) — contributed 2 concept elements to this direction.
Gaussian Interference Channel Capacity to Within One Bit: the General Case (2007) — contributed 1 concept elements to this direction.
Lattice Strategies for the Dirty Multiple Access Channel (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constant_gap_capacity_approximation_61c55470,
  title = {constant-gap capacity approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constant-gap-capacity-approximation/rdr_61c55470725049c5b1e23f7ba6c74279},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_constant_gap_capacity_approximation_61c55470_v1,
  title = {constant-gap capacity approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constant-gap-capacity-approximation/rdr_61c55470725049c5b1e23f7ba6c74279/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake