  In this paper, Space-Time Block Codes (STBCs) with reduced Sphere Decoding
Complexity (SDC) are constructed for two-user Multiple-Input Multiple-Output
(MIMO) fading multiple access channels. In this set-up, both the users employ
identical STBCs and the destination performs sphere decoding for the symbols of
the two users. First, we identify the positions of the zeros in the
$\textbf{R}$ matrix arising out of the Q-R decomposition of the lattice
generator such that (i) the worst case SDC (WSDC) and (ii) the average SDC
(ASDC) are reduced. Then, a set of necessary and sufficient conditions on the
lattice generator is provided such that the $\textbf{R}$ matrix has zeros at
the identified positions. Subsequently, explicit constructions of STBCs which
results in the reduced ASDC are presented. The rate (in complex symbols per
channel use) of the proposed designs is at most $2/N_{t}$ where $N_{t}$ denotes
the number of transmit antennas for each user. We also show that the class of
STBCs from complex orthogonal designs (other than the Alamouti design) reduce
the WSDC but not the ASDC.
