All scheduled dates:
Past
Title: How Non-Commutativity Helps Data Centers: Maximally Recoverable
Codes from Skew Polynomials
Abstract: Locally Repairable Codes (LRCs) allow for recovery from a
small number of erased symbols in a local manner based on just a few
other codeword symbols. A maximally recoverable (MR) LRC (also called
PMDS codes) offers the best possible blend of local and global erasure
resilience, guaranteeing recovery from all erasure patterns which are
information-theoretically correctable given the constraints of local
repair groups. This makes them attractive for use in distributed
storage systems where they have been deployed in certain parameter
regimes.
Random constructions easily show the existence of MR LRCs over very
large fields, but a major challenge is to construct MR LRCs, or even
show their existence, over smaller fields, as well as understand
inherent lower bounds on their field size. We will discuss a
construction based on skew polynomials (a non-commutative analog of
polynomial rings that dates back to (Ore, 1933)) that yields MR LRCs
over the smallest known alphabets in many practically relevant
parameter regimes, including matching a lower bound in an interesting
case.
The talk will introduce the concept of maximal recoverability, and
describe skew polynomials and non-singular matrices constructed using
them which lead to good MR LRCs. Time permitting, we will mention some
exciting recent connections between MR codes and list decoding, forged
by Brakensiek-Gopi-Makam in their work on higher order MDS codes.
Based on joint work with Sivakanth Gopi.
Title: Nonlinear Repair of Reed-Solomon Codes
Abstract: The problem of repairing linear codes, and in particular, Reed Solomon (RS) codes, has attracted a lot of attention in recent years due to its importance in distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. There are examples of RS codes with efficient repair schemes, and some are even optimal. However, these schemes fall short in several aspects; for example, they require a considerable field extension degree, and in particular, they do not work over prime fields. In this talk, we will explore the power of nonlinear repair schemes of RS codes and show that such schemes are crucial over prime fields, and in some cases, they outperform all linear schemes.
The talk is based on joint works with Noah Shutty, Itzhak Tamo, and Mary Wootters.
Title: Randomly Punctured Reed–Solomon Codes Achieve List-Decoding Capacity over Polynomial-Size Alphabets
Abstract: In this talk, I will introduce the essentials of a long line of work aimed at understanding the combinatorial list decodability of Reed–Solomon (RS) codes beyond the Johnson radius. More specifically, I will cover our recent result presented at FOCS 2023, showing that, with high probability, randomly punctured RS codes over fields of polynomial (specifically, quadratic) size achieve list-decoding capacity. The talk is based on joint work with Zeyu Guo.
Title: Error Correcting Codes in Recent Derandomization Results
Abstract: Recent years have seen exciting progress in the theory of derandomization. In particular, we now have new approaches to study derandomization under hardness assumptions, of both time- and space-bounded randomized computations. The advances in the area are often accompanied by new error correcting codes.
In the talk, I will give a survey of some of those derandomization results, and show how coding theory enters the picture. Most of the focus will be on fast and memory-efficient derandomization, that is, getting the optimal time and space overhead for our derandomized algorithm.
No prior knowledge in derandomization will be assumed.
Title: Bounds on the Probability of Decoding Error via Code Symmetry and Nesting
Abstract: Over the past 10 years, there have been significant advances in the understanding of sequences of structured error-correcting codes and their ability to achieve capacity. In particular, we now know that sequences of doubly-transitive codes achieve capacity on the binary erasure channel (BEC) and that sequences of Reed-Muller (RM) codes achieve capacity on binary-input memoryless symmetric (BMS) channels. This talk gives an overview of these results along with a simplified proof for RM codes on BMS channels. To conclude, some extensions and open problems are discussed.
Title: Star-products of codes: an Additive Combinatorics perspective.
Abstract: The star-product (also called Hadamard product or Schur product) of two codes C and D is the code generated by all coordinate-wise products of a word of C and a word of D. The star-product concept has been useful in a number of situations involving codes, including decoding, multiplicative secret-sharing, cryptanalysis, oblivious transfer reductions, and others. Every time one needs pairs of codes whose product has an unusually small dimension. Trying to characterise such pairs has much in common with problems in additive combinatorics where one is interested in pairs of sets whose sum has an unusually small cardinality. We will discuss this connection as well as some results for codes inspired by additive techniques.
Title: Interactive Coding with Small Memory and Improved Rate
Abstract: In this talk, I will discuss two-party interactive coding for adversarial noise, when both parties have limited memory. We will delve into our method of converting any protocol Π into a protocol Π′ that is not only robust to an ε-fraction of adversarial corruptions, but also uses small space. We will further show that this protocol matches the best known communication rate for protocols with no space restrictions.