  In the setting of quasi-static multiple-input multiple-output (MIMO)
channels, we consider the high signal-to-noise ratio (SNR) asymptotic
complexity required by the sphere decoding (SD) algorithm for decoding a large
class of full rate linear space-time codes. With SD complexity having random
fluctuations induced by the random channel, noise and codeword realizations,
the introduced SD complexity exponent manages to concisely describe the
computational reserves required by the SD algorithm to achieve arbitrarily
close to optimal decoding performance. Bounds and exact expressions for the SD
complexity exponent are obtained for the decoding of large families of codes
with arbitrary performance characteristics. For the particular example of
decoding the recently introduced threaded cyclic division algebra (CDA) based
codes -- the only currently known explicit designs that are uniformly optimal
with respect to the diversity multiplexing tradeoff (DMT) -- the SD complexity
exponent is shown to take a particularly concise form as a non-monotonic
function of the multiplexing gain. To date, the SD complexity exponent also
describes the minimum known complexity of any decoder that can provably achieve
a gap to maximum likelihood (ML) performance which vanishes in the high SNR
limit.
