Seminars

Spring 2019 - Geometric Complexity Theory

This semester I'll be participating in a seminar on Geometric Complexity Theory with Mauricio Velasco and Tristram Bogart. I don't know anything about the subject, so I'll be learning along with the students.

Fall 2018 - Topics in Coding Theory

Together with Mauricio Velasco and Tristram Bogart of Universidad de los Andes, I'm co-organizing a seminar titled "Topics in Coding Theory". The target audience is interested students at all levels, especially those writing a thesis in a related area.

Time and place: Wednesdays 11:00 - 11:45 in Z205.

Topics to be covered: There are no fixed topics for the seminar, and talks even tangentially related to Coding Theory are very welcome. However, here are some things I think are cool that I hope to cover this semester, and some suggestions for papers along these lines.

Locally Repairable Codes: A Locally Repairable Code (LRC) is one in which a lost symbol can be replaced by only computing a function of a few other symbols in the codeword. A lot about LRCs is known, such as bounds on the minimum distance and how to achieve these bounds, but a lot remains unknown. We hope to cover constructions of LRCs from Algebraic Geometry as well as decoding algorithms for such codes.
- A Family of Optimal Locally Recoverable Codes, https://arxiv.org/abs/1311.3284
- Optimal Locally Repairable Codes and Connections to Matroid Theory, https://arxiv.org/abs/1301.7693
- List Decoding of Locally Repairable Codes: https://arxiv.org/abs/1801.04229
- Codes with hierarchical locality from covering maps of curves: https://arxiv.org/abs/1807.05473
Private Search: Given a database X and a private record x, a Private Search algorithm allows us to search the database for all records x' such that d(x,x') < r for some set radius r. The trick is to do this without revealing much if anything about your private record x. Not much is known about how to do this, but throughout the semester I hope to explore some ideas.
- Efficient Storage and Retrieval by Content and Address of Static Files: https://dl.acm.org/citation.cfm?id=321812.321820
- The Asymptotic Capacity of Private Search: https://arxiv.org/abs/1801.05768
- Effective Proximity Retrieval by Ordering Permutations: https://ieeexplore.ieee.org/document/4378393/
Distributed Matrix Multiplication: Suppose we want to multiply two matrices A and B, but we don't have the computing power to do it. We might divide A and B up into several submatrices and outsource these smaller matrix multiplications to several servers. Coding Theory comes in to help us deal with unreliable, untrustworthy, or slow servers. For example, if A and B are both square matrices of size M x M, and each server is only willing to do one matrix multiplication of size M/2 x M/2, how many servers do we need to compute A*B? What if we want to allow for the possibility that two of the servers never respond, or only want to wait for say, the fastest four servers?
- Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication: https://arxiv.org/abs/1705.10464
- Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding: https://arxiv.org/abs/1801.07487

Schedule:

22.8 - Introduction and Brief Remarks - David Karpuk
29.8 - Private Search I - David Karpuk
5.9 - Private Search II - David Karpuk
12.9 - Locally Repairable Codes I - Mauricio Velasco
19.9 - Lagrange Coded Computation - David Jaramillo
26.9 - NO SEMINAR - Dave in the US
3.10 - NO SEMINAR - Semana de receso
10.10 - Locally Repairable Codes II - Mauricio Velasco
17.10 - Packings in the Grassmannian I - Tomás Bermúdez
24.10 - Packings in the Grassmannian II - Tomás Bermúdez
31.10 - Codes and Lattices - Martin Wosnitzka
7.11 - Tristram Bogart
14.11 - Secure Distributed Matrix Multiplication - David Karpuk
21.11 - Space-Time Codes from Division Algeberas - Jerson Caro
28.11 - Post-Mortem

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. Here are the topics and papers we covered this semester:

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?

A Survey on Network Codes for Distributed Storage, https://arxiv.org/abs/1004.4438
Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction, https://arxiv.org/abs/1005.4178

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.

Interference alignment for the MIMO interference channel, https://arxiv.org/abs/1303.5678
Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions, https://arxiv.org/abs/1005.1634

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