One of the most popular ways to exploit the advantages of a multiple-input multiple-output (MIMO) system is using space time block coding. A space time block code (STBC) is a finite set of complex matrices whose entries consist of the information symbols to be transmitted. A linear STBC is one in which the information symbols are linearly combined to form a two-dimensional code matrix. A well known method of maximum-likelihood (ML) decoding of such STBCs is using the sphere decoder (SD). In this thesis, new constructions of STBCs with low sphere decoding complexity are presented and various ways of characterizing and reducing the sphere decoding complexity of an STBC are addressed. The construction of low sphere decoding complexity STBCs is tackled using irreducible matrix representations of Clifford algebras, cyclic division algebras and crossed-product algebras. The complexity reduction algorithms for the STBCs constructed are explored using tree based search algorithms. Considering an STBC as a vector space over the set of weight matrices, the problem of characterizing the sphere decoding complexity is addressed using quadratic form representations. The main results are as follows. A sub-class of fast decodable STBCs known as Block Orthogonal STBCs (BOSTBCs) are explored. A set of sufficient conditions to obtain BOSTBCs are explained. How the block orthogonal structure of these codes can be exploited to reduce the SD complexity of the STBC is then explained using a depth first tree search algorithm. Bounds on the SD complexity reduction and its relationship with the block orthogonal structure are then addressed. A set of constructions to obtain BOSTBCs are presented next using Clifford unitary weight designs (CUWDs), Coordinate-interleaved orthogonal designs (CIODs), cyclic division algebras and crossed product algebras which show that a lot of codes existing in literature exhibit the block orthogonal property. Next, the dependency of the ordering of information symbols on the SD complexity is discussed following which a quadratic form representation known as the Hurwitz-Radon quadratic form (HRQF) of an STBC is presented which is solely dependent on the weight matrices of the STBC and their ordering. It is then shown that the SD complexity is only a function of the weight matrices defining the code and their ordering, and not of the channel realization (even though the equivalent channel when SD is used depends on the channel realization). It is also shown that the SD complexity is completely captured into a single matrix obtained from the HRQF. Also, for a given set of weight matrices, an algorithm to obtain a best ordering of them leading to the least SD complexity is presented using the HRQF matrix.