Search

We investigate adversarial network coding and decoding focusing on the multishot regime. Errors can occur on a proper subset of the network edges and are modeled via an adversarial channel. The paper contains both bounds and capacity-achieving schemes for the Diamond Network and the Mirrored Diamond Network. We also initiate the study of the generalizations of these networks.

We introduce the class of rank-metric geometric lattices and initiate the study of their structural properties. Rank-metric lattices can be seen as the q-analogues of higher-weight Dowling lattices, defined by Dowling himself in 1971. We fully characterize the supersolvable rank-metric lattices and compute their characteristic polynomials. We then concentrate on small rank-metric lattices whose characteristic polynomial we cannot compute, and provide a formula for them under a polyno-miality assumption on their Whitney numbers of the first kind. The proof relies on computational results and on the theory of vector rank-metric codes, which we review in this paper from the perspective of rank-metric lattices. More precisely, we introduce the notion of lattice-rank weights of a rank-metric code and inves-tigate their properties as combinatorial invariants and as code distinguishers for inequivalent codes.Mathematics Subject Classifications: 05A15, 06C10, 94B99 Irish Research Council [GOIPG/2018/2534]; Dutch Research Council [VI.Vidi.203.045, OCENW.KLEIN.539]; Royal Academy of Arts and Sciences of the Netherlands Published version Supported by the Irish Research Council, grant n. GOIPG/2018/2534. Supported by the Dutch Research Council through grants VI.Vidi.203.045, OCENW.KLEIN.539, and by the Royal Academy of Arts and Sciences of the Netherlands.

In this work we introduce a new class of optimal tensor codes related to the Ravagnani-type anticodes, namely the $j$-tensor maximum rank distance codes. We show that it extends the family of $j$-maximum rank distance codes and contains the $j$-tensor binomial moment determined codes (with respect to the Ravagnani-type anticodes) as a proper subclass. We define and study the generalized zeta function for tensor codes. We establish connections between this object and the weight enumerator of a code with respect to the Ravagnani-type anticodes. We introduce a new refinement of the invariants of tensor codes exploiting the structure of product lattices of some classes of anticodes and we derive the corresponding MacWilliams identities. In this framework, we also define a multivariate version of the tensor weight enumerator and we establish relations with the corresponding zeta function. As an application we derive connections on the generalized tensor weights related to the Delsarte and Ravagnani-type anticodes.

Tensor codes were introduced by Roth in 1991 and defined to be subspaces of r-tensors where the ambient space is endowed with the tensor rank as a distance function. They are a natural generalization of the rank-metric codes introduced by Delsarte in 1978. These codes started to attract more attention in 2008 when Kötter and Kschischang proposed them as a solution to error amplification in network coding. The main theme of this dissertation is the study of combinatorial and structural properties of tensor codes. We introduce and investigate invariants of tensor codes and we classify families of them that show strong properties of rigidity and extremality. We devote the first part of this work to an overview on the body of theory developed to date for codes in the rank metric. We set up the general notation and provide the background needed in the remaining chapters. In this setting, we introduce the notion of anticodes in their general form. The approach we will use in this work will be based on these mathematical objects. In the second part of the thesis we focus on the study of algebraic invariants for vector and matrix rank-metric codes and, in particular, we generalized the theory of the zeta function for rank-metric codes developed in 2018 by Blanco-Chacón, Byrne, Duursma and Sheekey. At this point, the correct notion of optimality is needed and we classify families of codes whose invariants are either partially or entirely determined by their code parameters. As an application, we provide a generalization of the MacWilliams identities for rank-metric codes. Part of this investigation will be devoted to the study another parameter of rank-metric codes, namely their tensor rank. In 1978, Brockett and Dobkin established a connection between linear block codes and tensor rank of matrix codes, which provides a powerful tool for determining the tensor rank of codes in the rank metric. We determine the tensor rank of some space of matrices and we illustrate some consequences in coding theory. We dedicate the third part of this dissertation to invariants of tensor codes from an anticode perspective. More precisely, we initiate the theory of these algebraic objects by identifying four different classes of anticodes and investigating the related invariants. We also introduce classes of extremal tensor codes and we develop the theory of the zeta functions in the tensor case. We conclude this work on a combinatorial note by introducing the rank-metric lattices as the q-analogue of the higher-weight Dowling lattices. The latter were proposed by Dowling in 1971 in connection to a central problem in coding theory. In this part, we fully characterize the rank-metric lattices that are supersolvable and we derive closed formulas for their Whitney numbers and characteristic polynomial. Finally, we establish a connection between these lattices and the problem of distinguishing between inequivalent rank-metric codes.

In 1991, Roth introduced a natural generalization of rank metric codes, namely tensor codes. The latter are defined to be subspaces of $r$-tensors where the ambient space is endowed with the tensor rank as a distance function. In this work, we describe the general class of tensor codes and we study their invariants that correspond to different families of anticodes. In our context, an anticode is a perfect space that has some additional properties. A perfect space is one that is spanned by tensors of rank 1. Our use of the anticode concept is motivated by an interest in capturing structural properties of tensor codes. In particular, we indentify four different classes of tensor anticodes and show how these gives different information on the codes they describe. We also define the generalized tensor binomial moments and the generalized tensor weight distribution of a code and establish a bijection between these invariants. We use the generalized tensor binomial moments to define the concept of an $i$-tensor BMD code, which is an extremal code in relation to an inequality arising from them. Finally, we give MacWilliams identities for generalized tensor binomial moments., 25 pages

A well studied problem in algebraic complexity theory is the determination of the complexity of problems relying on evaluations of bilinear maps. One measure of the complexity of a bilinear map (or 3-tensor) is the optimal number of non-scalar multiplications required to evaluate it. This quantity is also described as its tensor rank, which is the smallest number of rank one matrices whose span contains its first slice space. In this paper we derive upper bounds on the tensor ranks of certain classes of $3$-tensors and give explicit constructions of sets of rank one matrices containing their first slice spaces. We also show how these results can be applied in coding theory to derive upper bounds on the tensor rank of some rank-metric codes. In particular, we compute the tensor rank of some families of $\mathbb{F}_{q^m}$-linear codes and we show that they are extremal with respect to Kruskal's tensor rank bound., 24 pages