CanaDAM 2017
Ryerson University, June 12 - 16, 2017

Locality in Coding Theory
Org: Parikshit Gopalan (VMWare)

MDS codes with optimal regeneration  [PDF]

The repair problem is a recent direction in coding theory, motivated by the need to increase reliability of distributed storage systems. We say that a code over a field $F_q$ can be repaired optimally if the number of field symbols used to correct an erasure (the "repair bandwidth") meets the so-called cut-set bound on this quantity. We present constructions of MDS array codes with optimal repair bandwidth for any given number of parity symbols. We also discuss repair of Reed-Solomon codes, giving a construction of RS codes with asymptotically optimal repair. Based on joint works with Min Ye (UMD).

Locally Recoverable Codes  [PDF]

Locally Recoverable Codes aka LRCs are a flavor of codes with desirable locality guarantees that have been studied in the context of distributed storage. They give strong worst-case guarantees but additionally ensure quick and easy recovery from typical failure scenarios. At a first cut, "typical" was taken to mean few failures, but there have been recent attempts to model more complex correlated failures. This talk will briefly survey the main insights in this area and open problems.

2-Server PIR with sub-polynomial communication  [PDF]

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the i'th bit of an n-bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. The privacy of the user is information theoretic and does not rely on any cryptographic assumptions. In this work we construct a new 2-server PIR scheme with total communication cost $n^{o(1)}$ matching previously known results for 3 servers. The main ingredient in these protocols is a combinatorial construction of Grolmusz called Matching Vector Families, and our protocol uses polynomial interpolation using partial derivatives.

Locally-testable and locally-correctable codes approaching the Gilbert-Varshamov bound  [PDF]

I will talk about a new binary error-correcting codes which combine local testability and local correctability, usually associated with rigid algebraic codes, with the best known rate-distance tradeoff, usually associated with random codes.

Based on joint work with Sivakanth Gopi, Rafael Oliveira, Noga Ron-Zewi and Shubhangi Saraf

MDS Codes with Small Sub-packetization and Near-optimal Repair Bandwidth  [PDF]

Minimum storage regenerating (MSR) codes form a special class of maximum distance separable (MDS) codes by providing mechanisms for exact regeneration of a single code-block by downloading the minimum amount of information from the remaining code-blocks. As a result, the MSR codes find application to distributed storage systems to ensure node repairs with optimal repair-bandwidth. However, constructions of MSR codes require large sub-packetization levels, which restricts their employment in practice. In this talk, I’ll present two general approaches to construct MDS codes that significantly reduce the required sub-packetization level by incurring slightly higher repair-bandwidth as compared to the MSR codes.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Ryerson University Office of Naval Research Science and Technology