The Taub Faculty of Computer Science Events and Talks

The interest in subspace codes has increased lately due to their application in error correction for random network coding. A subspace code is a collection of subspaces of a vector space under the subspace distance $d_s(U,V)=\dim U + \dim V-2\dim(U\cap V)$. In this dissertation we discuss both purely mathematical and practical questions which involve subspace codes. The theoretical part of this work concerns a few special cases of subspace codes. Equidistant subspace codes, in which the distance between any two codewords is identical, are discussed, and bounds and constructions are given. Cyclic subspace codes, which are closed under multiplication by a field element are discussed, and the first non-trivial construction of those is given by using subspace polynomials. The latter topic is related to showing the limits of list-decoding Gabidulin and subspace codes, improving previously known bounds. The practical aspect of this work concerns distributed storage systems. A distributed storage system is comprised of storage nodes with communication links, and the system is required to maintain reliability over time. The aforementioned equidistant subspace codes are shown to be useful for devising a minimum bandwidth regenerating code (MBR) for distributed storage systems, a minimum storage regenerating code (MSR) is constructed using subspace techniques, and finally, the question of local erasure correction in permutations is discussed, under the motivation of performing updates to a distributed storage system.