Spring 2018 - Algebraic Methods in Data Storage

Together with Mauricio Velasco of Los Andes and Valerie Gauthier of Universidad del Rosario, I'm co-organizing a seminar on applications of algebra in data storage. The target audience is students at all levels looking to write a thesis in algebra or applied mathematics, as well as anyone interested in taking up research in or just learning more about the topic.

Students are expected to be active participants in the seminar and give at least one presentation, especially those looking to write a thesis in a related topic.

Below are some of the topics and articles we hope to briefly cover. If you'd like to present any of these papers, or have some other topic in mind that you think would be interesting and relevant, please let me know and we can put you in the schedule!

Registration: If you're coming from outside Los Andes to attend the seminar, please register each week using the following Google Doc. It will make it much easier for us to get you access to the university. If you're from Los Andes, we'd appreciate you registering as well, since it will help us know how many people to expect.

Room Info: Fridays at 9AM in Z205

Tentative Schedule:

1.26 - Brief Organizational Meeting

2.2 - An Introduction to Distributed Storage Systems - David Karpuk

9.2 - Network Coding for Distributed Storage Systems - David Karpuk

16.2 - Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction - David Jaramillo

23.2 - Locally Repairable Codes - Mauricio Velasco

2.3 - A Family of Optimal Locally Recoverable Codes - Mauricio Velasco

9.3 - Optimal Locally Repairable Codes and Connections to Matroid Theory - Tristram Bogart

16.3 - Locally Recoverable Codes on Algebraic Curves - Jerson Caro

23.3 - An Introduction to Private Information Retrieval - David Karpuk

30.3 - NO SEMINAR.

6.4 - The Capacity of Private Information Retrieval - Simón Soto

13.4 - NO SEMINAR.

20.4 - The Capacity of Private Information Retrieval from Coded Databases - Nicolas Escobar

27.4 - Post-Quantum Cryptography - Valerie Gauthier

4.5 - Post-Quantum Cryptography and the McEliece Cryptosystem - Daniel Toloso

11.5 - Interference alignment for the MIMO interference channel - Daniel Tamayo

Distributed Storage Systems - Server failure is common in large data centers, and linear coding is often used to add redundancy to such systems to safeguard data. What are the fundamental limits of distributed storage systems? In case of a lost node, what is the most efficient way to repair the system?

Additionally, here are some notes I wrote up when I was a postdoc, which do in detail a simple example of an MSR code which uses Interference Alignment during node repair. There is also some attempt at phrasing the whole problem solely in algebraic terms.


Locally Repairable Codes - The locality of a linear code measures how many other entries we need to recover lost entries of codewords. Locally repairable codes are one in which the required number of entries is small, and have applications in data storage. The best such codes arise from evaluating vector spaces of polynomial functions on curves.

Private Information Retrieval - Private Information Retrieval (PIR) asks the question of how to download a file privately from a database, without revealing the identity of the downloaded file to the database. The rate of a PIR protocol measures its efficiency, and Reed-Solomon and Reed-Muller codes (certain classes of evaluation codes) are particularly useful in constructing PIR protocols with high rate.

Interference Alignment - Interference is a major bottleneck in wireless networks with many users. A new technique to manage interference, known as Interference Alignment (IA), seeks to minimize the effect of interference by having interfering subspaces overlap at the receiver. Techniques from Algebraic Geometry are especially effective, and ideas from IA can be applied to efficiently repair nodes in distributed storage systems.

Cryptography - Cryptographic techniques allow for the secure transmission of data in the presence of eavesdroppers. The difficulty of solving the discrete logarithm problem on elliptic curves makes them prime candidates for use in key exchanges. With the advent of quantum computing on the horizon, many traditional protocols based on e.g. integer factorization will no longer be secure. However, techniques from post-quantum cryptography, such as coding-based cryptography, promise security even against quantum attacks.