CSS-T CODE WITH NON-VANISHING RATES FROM REED-MULLER CODES.

CSS-T codes are a class of stabilizer codes introduced by Rengaswamy et al with desired properties for quantum fault-tolerance. In this work, we give a comprehensive study of non-degerate CSS-T codes built from Reed-Muller codes. These classical codes allow for the construction of CSS-T code families with non-vanishing asymptotic rate up to and possibly diverging minimum distance when non-degenerate.

RECURSIVE EDGE TOGGLING FOR CONSTRUCTION OF DE BRUIJN SEQUENCES

De Bruijn sequences are cyclic sequences of length that contain every binary word of length exactly once. The construction of many such sequences of a given order is useful for the generation of stream ciphers. One method of constructing sequences makes use of a homomorphism from the de Bruijn graph of order to the graph of order . The preimages of a de Bruijn sequence under this homomorphism form two cycles which may be joined at certain points. We examine a par- ticular method for identifying such points when the sequence in question is recursively constructed in this manner. Using the structure of the con- struction, we are able to calculate sums of subsequences in 􏰁 time, and the location of a given word in time. Together, these functions allow a check to be made for the validity of any potential toggle point. This provides a method for efficiently generating a recursive specification for such sequences, each successful step of which takes , for from 3 to n.

EXTERNAL CODES FOR MULTIPLE UNICAST NETWORKS VIA INTERFERENCE ALIGNMENT

We introduce a formal framework to study the multiple unicast problem for a coded network in which the network code is linear over a finite field and fixed. We show that the problem corresponds to an interference alignment problem over a finite field. In this context, we establish an outer bound for the achievable rate region and provide examples of networks where the bound is sharp. We finally give evidence of the crucial role played by the field characteristic in the problem.

GENERIC ERROR SDP AND GENERIC ERROR CVE

This paper introduces a new family of CVE schemes built from generic errors (GE-CVE) and identifies a vulnerability therein. To introduce the problem, we generalize the concept of error sets beyond those defined by a metric, and use the set-theoretic difference operator to characterize when these error sets are detectable or correctable by codes. We prove the existence of a general, metric-less form of the Gilbert-Varshamov bound, and show that - like in the Hamming setting - a random code corrects a generic error set with overwhelming probability. We define the generic error SDP (GE-SDP), which is contained in the complexity class of NP-hard problems, and use its hardness to demonstrate the security of GE-CVE. We prove that these schemes are complete, sound, and zero-knowledge. Finally, we identify a vulnerability of the GE-SDP for codes defined over large extension fields and without a very high rate. We show that certain GE-CVE parameters suffer from this vulnerability, notably the restricted CVE scheme.

ROOT OF UNITY FOR SECURE DISTRIBUTED MATRIX MULTIPLICATION: GRID PARTITION CASE.

We consider the problem of secure distributed matrix multiplication (SDMM), where a user has two matrices and wishes to compute their product with the help of N honest but curious servers under the security constraint that any information about either A or B is not leaked to any server. This paper presents a new scheme that considers a grid product partition for matrices A and B, which achieves an upload cost significantly lower than the existing results in the literature. Also, it significantly reduces the recovery threshold compared to the PolyDot codes presented for grid partition when T > 0. Since the grid partition is a general partition that incorporates the inner and outer ones, it turns out that the communication load of the proposed scheme matches the best-known protocols for those extreme cases.

BATCH CODES FROM AFFINE CARTESIAN CODES AND QUOTIENT SPACES

Affine Cartesian codes are defined by evaluating multivariate polynomials at a cartesian product of finite subsets of a finite field. In this work we examine properties of these codes as batch codes. We consider the recovery sets to be defined by points aligned on a specific direction and the buckets to be derived from cosets of a subspace of the ambient space of the evaluation points. We are able to prove that under these conditions, an affine Cartesian code is able to satisfy a query of size up to one more than the dimension of the space of the ambient space.

A PARALLEL JACOBI-EMBEDDED GAUSS-SEIDEL METHOD.

A broad range of scientific simulations involve solving large-scale computationally expensive linear systems of equations. Iterative solvers are typically preferred over direct methods when it comes to large systems due to their lower memory requirements and shorter execution times. However, selecting the appropriate iterative solver is problem-specific and dependent on the type and symmetry of the coefficient matrix. Gauss-Seidel (GS) is an iterative method for solving linear systems that are either strictly diagonally dominant or symmetric positive definite. This technique is an improved version of Jacobi and typically converges in fewer iterations. However, the sequential nature of this algorithm complicates the parallel extraction. In fact, most parallel derivatives of GS rely on the sparsity pattern of the coefficient matrix and require matrix reordering or domain decomposition. In this article, we introduce a new algorithm that exploits the convergence property of GS and adapts the parallel structure of Jacobi. The proposed method works for both dense and sparse systems and is straightforward to implement. We have examined the performance of our method on multicore and many-core architectures. Experimental results demonstrate the superior performance of the proposed algorithm compared with GS and Jacobi. Additionally, performance comparison with built-in Krylov solvers in MATLAB showed that in terms of time per iteration, Krylov methods perform faster on CPUs, but our approach is significantly better when executed on GPUs. Lastly, we apply our method to solve the power flow problem, and the results indicate a significant improvement in runtime, reaching up to 87 times faster speed compared with GS.

HILBERT MODULAR FORMS AND CODES OVER

Let be an odd prime and consider the finite field . Given a linear code , we use algebraic number theory to construct an associated lattice for an algebraic number field and the ring of integers of . We attach a theta series to the lattice and prove a relation between and the complete weight enumerator evaluated on weight one theta series.

MULTICAST TRIANGULAR SEMILATTICE NETWORK.s

We investigate the structure of the code graph of a multicast network that has a characteristic shape of an inverted equilateral triangle. We provide a criterion that determines the validity of a receiver placement within the code graph, present invariance properties of the determinants corresponding to receiver placements under symmetries, and provide a complete study of these networks’ receivers and required field sizes up to a network of 4 sources. We also improve on various definitions related to code graphs.

AFFINE CARTESIAN CODES WITH COMPLEMENTARY DUALS

A linear code with the property that is said to be a linear complementary dual, or LCD, code. In this paper, we consider generalized affine Cartesian codes which are LCD. Generalized affine Cartesian codes arise naturally as the duals of affine Cartesian codes in the same way that generalized Reed–Solomon codes arise as duals of Reed–Solomon codes. Generalized affine Cartesian codes are evaluation codes constructed by evaluating multivariate polynomials of bounded degree at points in an m-dimensional Cartesian set over a finite field K and scaling the coordinates. The LCD property depends on the scalars used. Because Reed–Solomon codes are a special case, we obtain a characterization of those generalized Reed–Solomon codes which are LCD along with the more general result for generalized affine Cartesian codes. These results are independent of the characteristic of the underlying field.

MATROIDAL ROOT STRUCTURE OF SKEW POLYNOMIALS OVER FINITE FIELDS

A skew polynomial ring is a ring of polynomials with non-commutative multiplication. This creates a difference between left and right divisibility, evaluations, and roots. A polynomial in such a ring may have more roots than its degree, which leads to the concepts of closures and independent sets of roots. In , this leads to the matroids and of right independent and left independent sets, which are isomorphic via the extension of the map defined by , where . Extending the field of coefficients of R results in a new ring of which is a subring, and if the extension is taken to include roots of an evaluation polynomial of , then all roots of in are in the same conjugacy class.

BATCH CODES FROM HAMMING AND REED-MULLER CODES

Batch codes, introduced by Ishai et al., encode a string into an -tuple of strings, called buckets. In this paper we consider multiset batch codes wherein a set of -users wish to access one bit of information each from the original string. We introduce a concept of optimal batch codes. We first show that binary Hamming codes are optimal batch codes. The main body of this work provides batch properties of Reed-Muller codes. We look at locality and availability properties of first order Reed-Muller codes over any finite field. We then show that binary first order Reed-Muller codes are optimal batch codes when the number of users is 4 and generalize our study to the family of binary Reed-Muller codes which have order less than half their length.

REPRESENTATIONS OF THE MULTICAST NETWORK PROBLEM

We approach the problem of linear network coding for multicast networks from different perspectives. We introduce the notion of the coding points of a network, which are edges of the network where messages combine and coding occurs. We give an integer linear program that leads to choices of paths through the network that minimize the number of coding points. We introduce the code graph of a network, a simplified directed graph that maintains the information essential to understanding the coding properties of the network. One of the main problems in network coding is to understand when the capacity of a multicast network is achieved with linear network coding over a finite field of size q. We explain how this problem can be interpreted in terms of rational points on certain algebraic varieties.

CODES FOR DISTRIBUTED STORAGE FROM 3-REGULAR GRAPHS

This paper considers distributed storage systems (DSSs) from a graph theoretic perspective. A DSS is constructed by means of the path decomposition of a 3-regular graph into paths. The paths represent the disks of the DSS and the edges of the graph act as the blocks of storage. We deduce the properties of the DSS from a related graph and show their optimality.

MATROIDAL STRUCTURE OF SKEW POLYNOMIAL RINGS WITH APPLICATION TO NETWORK CODING

Over a finite field , the evaluation of skew polynomials is intimately related to the evaluation of linearized polynomials. This connection allows one to relate the concept of polynomial independence defined for skew polynomials to the familiar concept of linear independence for vector spaces. This relation allows for the definition of a representable matroid called the -matroid, with rank function that makes it a metric space. Specific submatroids of this matroid are individually bijectively isometric to the projective geometry of equipped with the subspace metric. This isometry allows one to use the -matroid in a matroidal network coding application.

CONSTRUCTION AND DECODING OF GENERALIZED SKEW-EVALUATION CODES

Skew polynomials are elements of a noncommutative ring that, in recent years, have found applications in coding theory and cryptography. Skew polynomials have a well-defined evaluation map. This map leads to the definition of a class of codes called Generalized Skew-Evaluation codes that contains Gabidulin codes as a special case as well as other related codes with additional desirable properties. A Berlekamp-Welch-type decoder for an important class of these codes can be constructed using Kötter interpolation in skew polynomial rings.

SPREAD DECODING IN EXTENSION FIELDS

A spread code is a set of vector spaces of a fixed dimension over a finite field with certain properties used for random network coding. It can be constructed in different ways which lead to different decoding algorithms. In this work we consider one such representation of spread codes and present a minimum distance decoding algorithm which is efficient when the code words, the received space and the error space have small dimension.

CYCLIC ORBIT CODES

A constant dimension code consists of a set of k-dimensional subspaces of . Orbit codes are constant dimension codes which are defined as orbits of a subgroup of the general linear group, acting on the set of all subspaces of . If the acting group is cyclic, the corresponding orbit codes are called cyclic orbit codes. In this paper, we show how orbit codes can be seen as an analog of linear codes in the block coding case. We investigate how the structure of cyclic orbit codes can be utilized to compute the minimum distance and cardinality of a given code and propose different decoding procedures for a particular subclass of cyclic orbit codes.

KÖTTER INTERPOLATION IN SKEW POLYNOMIAL RINGS

Skew polynomials are a noncommutative generalization of ordinary polynomials that, in recent years, have found applications in coding theory and cryptography. Viewed as functions, skew polynomials have a well-defined evaluation map; however, little is known about skew-polynomial interpolation. In this work, we apply Kötter’s interpolation framework to free modules over skew polynomial rings. As a special case, we introduce a simple interpolation algorithm akin to Newton interpolation for ordinary polynomials.

AN ALGEBRAIC APPROACH FOR DECODING SPREAD CODES

In this paper we study spread codes: a family of constant-dimension codes for random linear network coding. In other words, the codewords are full-rank matrices of size with entries in a finite field . Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires operations over an extension field . Our algorithm is more efficient than the previous ones in the literature, when the dimension of the codewords is small with respect to . The decoding algorithm takes advantage of the algebraic structure of the code, and it uses original results on minors of a matrix and on the factorization of polynomials over finite fields.

SPREAD CODES AND MORE GENERAL NETWORK CODES

ON CONJUGACY CLASSES OF SUBGROUPS OF THE GENERAL LINEAR GROUP AND CYCLIC ORBIT CODES

Orbit codes are a family of codes applicable for communications on a random linear network coding channel. The paper focuses on the classification of these codes. We start by classifying the conjugacy classes of cyclic subgroups of the general linear group. As a result, we are able to focus the study of cyclic orbit codes to a restricted family of them.

ORBIT CODES — A NEW CONCEPT IN THE AREA OF NETWORK CODING

We introduce a new class of constant dimension codes called orbit codes. The basic properties of these codes are derived. It will be shown that many of the known families of constant dimension codes in the literature are actually orbit codes.

ON CONJUGACY CLASSES OF SUBGROUPS OF THE GENERAL LINEAR GROUP AND CYCLIC ORBIT CODES

In this paper we introduce the class of spread codes for the use in random network coding. Spread codes are based on the construction of spreads in finite projective geometry. The major contribution of the paper is an efficient decoding algorithm of spread codes up to half the minimum distance.

COMPUTATION OF THE WEIGHT DISTRIBUTION OF CRC CODES

In this article, we illustrate an algorithm for the computation of the weight distribution of CRC codes. The recursive structure of CRC codes will give us an iterative way to compute the weight distribution of their dual codes starting from some “representative” words. Thanks to MacWilliams’ Theorem, the computation of the weight distribution of the dual codes can be easily brought back to that of CRC codes.

CALCOLO DELLA DISTRIBUZIONE DEI PESI NEI CODICI CICLICI ACCORCIATI