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. https://docs.google.com/forms/d/e/1FAIpQLSewZ6Ng2tVtz1_EWOApUZV3OZmbT44lGFrsb57PiDAtMTYR_Q/viewform
Room Info: Fridays at 9AM in Z205
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.
- Locally Repairable Codes, https://arxiv.org/abs/1206.3804
- A Family of Optimal Locally Recoverable Codes, https://arxiv.org/abs/1311.3284
- Locally Recoverable Codes on Algebraic Curves, https://arxiv.org/abs/1603.08876
- Optimal Locally Repairable Codes and Connections to Matroid Theory, https://arxiv.org/abs/1301.7693
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.
- The Capacity of Private Information Retrieval, https://arxiv.org/abs/1602.09134
- The Capacity of Private Information Retrieval from Coded Databases, https://arxiv.org/abs/1609.08138
- Private Information Retrieval from Coded Databases with Colluding Servers, https://arxiv.org/abs/1611.02062 (note: I'm a co-author on this paper)
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.
- Elliptic Curves: Number Theory and Cryptography, by Larry Washington. See especially chapters 5, 6, and 13.
- McEliece cryptosystem, https://en.wikipedia.org/wiki/McEliece_cryptosystem (a better reference coming soon!)
- Lattice Codes for the Wiretap Gaussian Channel: Construction and Analysis, https://arxiv.org/abs/1103.4086