Complexity analysis for ML-based sphere decoder achieving a vanishing performance-gap to brute force ML decoding

This work identifies the computational reserves required for the maximum likelihood (ML)-based sphere decoding solutions that achieve, in the high-rate and high-SNR limit, a vanishing gap to the error-performance of the optimal brute force ML decoder. These error performance and complexity guarantees hold for most multiple-input multiple-output scenarios, all reasonable fading statistics, all channel dimensions and all full-rate lattice codes. The analysis also identifies a rate-reliability-complexity tradeoff establishing concise expressions for the optimal diversity gain achievable in the presence of any run-time constraint imposed due to the unavailability of enough computational resources required to achieve a vanishing gap.