Schedule for: 22w5180 - Algebraic Methods in Coding Theory and Communication

This talk provides an introduction to the theory of locally recoverable codes (LRCs). In particular, we cover the basics on LRCs (motivation, definition, and singleton bound) and survey recent advances, with particular emphasis on Tamo-Barg codes and their connection to Galois theory over global function fields.

There has been much recent work on erasure recovery using either fewer symbols or less information from a received word. In particular, locally recoverable codes and linear exact repair schemes address these scenarios. In this talk, we consider a similar challenge for error correction. Decoding algorithms for error-correcting codes typically take as input all symbols of a received word and attempt to determine the original codeword. Fractional decoding attempts to do so using only a portion of the information normally used in recovery. In this talk, we consider how this framework developed in earlier works by Tamo, Ye, and Barg and Santos may be applied to codes defined using curves. This is joint work with Aidan Murphy and Welington Santos.

We extend the notion of locality from the Hamming metric to the rank and subspace metrics. Our main contribution is to construct a class of array codes with locality constraints in the rank metric. Our motivation for constructing such codes stems from designing codes for efficient data recovery from correlated and/or mixed (i.e., complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from 'crisscross errors and erasures', which affect a limited number of rows and/or columns of the storage system. We also derive a Singleton-like upper bound on the minimum rank distance of (linear) codes with 'rank-locality' constraints. Our proposed construction achieves this bound for a broad range of parameters. The construction builds upon Tamo and Barg's method for constructing locally repairable codes with optimal minimum Hamming distance. Finally, we construct a class of constant-dimension subspace codes (also known as Grassmannian codes) with locality constraints in the subspace metric. The key idea is to show that a Grassmannian code with locality can be easily constructed from a rank-metric code with locality by using the lifting method proposed by Silva et al. We present an application of such codes for distributed storage systems, wherein nodes are connected over a network that can introduce errors and erasures.

A (linear) rank-metric codes is a vector space of matrices of given size over a finite field, in which the rank of any nonzero matrix is bounded from below by a given integer. Rank-metric codes were first studied for combinatorial interest by Delsarte in the seventies, and then by Cooperstein, Gabidulin, and Roth in various contexts. In 2008, Silva, Koetter and Kschischang discovered that rank-metric codes combined with linear network coding offer a solution to the problem of error amplification in communication networks. Since then, rank-metric codes have been a thriving research area within coding theory, electrical engineering, and discrete mathematics. This talk offers an overview on the mathematical theory of rank-metric codes, from the problem of correcting errors in networks, to that of investigating the properties of certain combinatorial structures and their q-analogues.

In the worst-case (bit)-deletion noise model, a subset of up to t arbitrarily chosen bits are deleted from a sequence of n codeword bits. Crucially, the locations of the deleted bits are not known to the receiver who receives a subsequence of the transmitted bit-string. The goal is to design codes of low redundancy that allow recovery of the deleted bits and the original codeword. The study of deletion-correcting codes itself is quite old, dating back to optimal single-deletion codes in the 1960s, and positive rate codes to correct t = Ω(n) deletions in the 1990s. However, many basic questions remained open and our understanding of deletion-correcting codes significantly lagged the vast literature concerning error-correcting codes to correct bit flips. After a long hiatus, there has been notable progress on deletion-correcting codes in the last 6-7 years, covering regimes when the number of deletions t is a small constant, a small constant fraction of n, and a large proportion of n, as well as the list-decoding model. The talk will survey some of this progress.

Consider an assignment of bits to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length |V| on G. If G contains many cliques, it is easy to construct storage codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where finding codes of rate >1/2 is a nontrivial task. Previously only isolated examples of storage codes of rate ≥ 1/2 on triangle-free graphs were given in the literature. The class of graphs that we consider is coset graphs of linear binary codes (Cayley graphs of the group $\mathbb{F}_{2^r}$). One of the main results of this work is an infinite family of linear storage codes with rate approaching 3/4. We also give a group of necessary conditions for such codes to have rate potentially close to 1 and state a number of open problems. Joint work with Gilles Zémor.

We will introduce the basics of code-based crypto systems and give an overview of past and current developments. We will start with the original public key cryptosystems by McEliece and Niederreiter, discuss several variants in the Hamming and rank metric of these systems and talk about various tools for cryptanalyzing them. In the end we will mention results on using other metrics for these systems and some techniques for creating digital signatures from the syndrome decoding problem.

In this talk we survey recent results for rank-based cryptography: cryptosystems which are based on error-correcting codes embedded with the rank metric. These new results concern the LRPC cryptosystem and the RQC cryptosystems for which we propose a new approach which permits to decrease public key by roughly 30% and permits to obtain very efficient systems even in the case of proven 2^-128 Decryption Failure Rate. We will also survey different type of signatures based on rank metric including the Durandal signature scheme. Overall these new results show the validity of rank metric based cryptography as a real alternative in post-quantum crypto.

Code-based cryptography, in particular the McEliece cryptosystem with binary Goppa codes, is known as one of the most conservative choices in post-quantum cryptography. It is also known as a system that is impractical or cumbersome to use for Internet applications due to the large size of the public key. Among the candidates in the 3rd round of the NIST competition on post-quantum cryptography is also the system with the smallest ciphertext size, making it attractive in situations where keys are changed infrequently and ciphertext size matters. This talk will present several recent applications of code-based cryptography in Internet applications.

Maximum information flow over a communication network with one source and one sink can be characterized by the classical max-flow min-cut theorem. However, in the multicast scenario (one source and multiple sinks), maximum flow cannot always be achieved by routing only. In 2000, Ahlswede, Cai, Li and Yeung developed a technique, called Network Coding, that allows the source to send the maximum possible amount of information to all sinks simultaneously. In this talk, we provide an introduction to Network Coding, and then provide a survey on techniques for deterministic worst-case error correction and information-theoretical security under the model considered by Koetter, Kschischang and Silva. This model considers the underlying network topology and network code as a blackbox (i.e., no knowledge or modification of the network is needed) and is thus compatible with random linear Network Coding. We will go through the different coding results obtained in the past decade, including subspace coding, list-decoding and multishot network coding, among others. We will conclude with directions for future research.

Distributed storage systems strive to maximize the number of concurrent data access requests they can support with fixed resources. Replicating data objects according to their relative popularity and access volume helps achieve this goal. However, these quantities are often unpredictable. In emerging applications such as edge computing, even the expected numbers of users and their data interests extensively fluctuate, and data storage schemes should support such dynamics. Erasure-coding has emerged as an efficient and robust form of redundant storage. In erasure-coded models, data objects are elements of a finite field. Each node in the system stores one or more linear combinations of data objects. This talk asks 1) which data access rates an erasure-coded system can support and 2) which codes can support a specified region of access rates. We will address these questions by formulating them as some known and some new combinatorial optimization problems on graphs. We will explain connections with LRC and batch codes. This talk will also describe how, instead of a combinatorial, one can adopt a geometric approach to the problem.

There are many connections between linear codes and matroids and several coding theoretic invariants turn out to be matroid invariants. Following the development of the theory of rank-metric codes, q-matroids and q-polymatroids have become a topic of interest among an increasing number of researchers, especially in the last few years. This topic involves submodular functions defined on the lattice of subspaces of a vector space. In this talk we'll look at some recent results of q-matroids and q-polymatroids and show the connections to rank metric codes. We will use the characteristic polynomial of a q-polymatroid as a basic tool for some of these results.

This talk will focus on the interactions between algebraic coding theory and finite geometry. We will explain in detail how these two mathematical areas are connected and in which way one can transform metric problems in coding theory to intersection problems in finite geometry, and vice versa. In particular, we will give an overview of such problems, from well-known results to more recent research directions.

In this talk, we intend to present the concept of footprint of an ideal, and a (certainly non-exhaustive) collection of recent results in coding theory obtained with the help of footprints and other tools from Gröbner basis theory.

The Hamming weight enumerator can be viewed in two ways: (1) as counting the number of entries in a codeword that belong to particular subsets of a partition of the alphabet, or (2) using the value of the weight as the exponent in the enumerator. In generalizing beyond the Hamming weight enumerator, the counting interpretation has enjoyed great success. In contrast, the w-weight enumerator determined by a weight w often fails to satisfy the MacWilliams identities. We will describe some of these failures for well-known weights.