"Underdetermined detection problems can arise in communications, e.g., multi-user detection for overloaded CDMA-based systems, MIMO systems with the number of receive antennas smaller than that of transmit antennas. They can be formulated as underdetermined integer least-square (ILS) problems, and many conventional suboptimal detection schemes lead to poor performance, whilst standard sphere-decoding (SD) algorithms, which can achieve optimal maximum-likelihood (ML) performance with low complexity for full-column-rank ILS systems, cannot be directly applied. The principal objective of this dissertation is to develop efficient detection algorithms based on SD for the underdetermined detection problems, which can approach the optimal performance. Most of Generalized SD (GSD) algorithms, recently proposed to solve undetermined ILS problems, have to transform an M-QAM constellation (with M>4) into multiple QPSKs, and hence result in unfavorably enlarged problem size and increased complexity. In contrast, this dissertation proposes a GSD algorithm (called lambda-GSD) by transforming the underdetermined system into a full-column-rank one and then utilizing SD algorithm on the transformed problem, which can circumvent the problematic size increase for high QAMs. As a result, the proposed lambda-GSD algorithm keeps the original problem size for all modulation constellations and the efficiency is considerably improved for M-QAM (with M>4). We perform union-bound performance analysis and derive the criterion to choose the design parameter lambda. The performance analysis shows that lambda-GSD can provide the exact optimum ML performance for constant-modulus constellations and an ML-approaching performance for non-constant-modulus constellations by judiciously choosing lambda. Theoretical complexity study is an important and challenging issue for an algorithm. By exploiting the underlying transformed matrix structure, we derive closed-form formulas to approximate the expected complexity of lambda-GSD for various modulation types. A lower bound on the expected complexity exponent is also analytically established. The consistency between the theoretical and simulation results on the number of searching FLOPS indicates that the analytical complexity formulas can capture the key complexity characteristics of the proposed lambda-GSD algorithm and can also serve as references for other GSD algorithms. To speed up the searching, we consider two following aspects. One is to propose an improved lambda-GSD version that alleviates the possible ill-conditioned transformed structure by a systematic method to choose lambda. The other is to develop efficient radius setting strategies. A linear-programming approach is used to calculate the initial radius for hard-decision SD and GSD; and a radius updating strategy combined with a simple initial radius setting is developed for soft-output list-sphere-decoding (LSD) and list-generalized-sphere-decoding (LGSD) algorithms, which reduces greatly the searching complexity as compared to the fixed radius setting strategy."--