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.
  • 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.
  • 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?


  • 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?

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.