LIDS Tea: A Family of MDS Codes on Generic Intersections

This talk describes a new method to construct maximum distance separable (MDS) codes. When they exist, MDS codes can correct the largest possible number of errors for a fixed rate and block length.  A celebrated example of this kind is the Reed-Solomon code, which is known to possess beautiful geometric structures while (perhaps for the same reason) being one of the most frequently used error-correcting codes in practice.

This talk starts with an overview of Reed-Solomon codes and their construction by evaluating polynomials along a set of collinear points. A set of collinear points has no distinguished subsets and it turns out this property can be used to produce many other MDS codes. In particular, evaluation along points in generic intersections (e.g., intersection of most two curves in a plane, most three surfaces in 3-space, etc.) gives rise to an MDS code. The main tools needed to prove this are the uniform position lemma of Harris and Rathmann and the Cayley-Bacharach theorem. Various properties of these MDS codes can be easily understood using the same tokens. In particular, their decoding properties beyond the error-correction threshold will be discussed.

About LIDS Tea: LIDS Tea talks are 20 minute long informal presentations for the purpose of sharing ideas and making others aware about some of the topics that may be of interest to the LIDS audience. If you are interested in presenting in the upcoming seminars, please email Marzieh Parandehgheibi or Yasin Yazicioglu.