报告题目：Efficient Linear and Affine Codes for Correcting Insertions/Deletions

报告人：程宽

报告时间：2021年12月03日14:00-15:00

报告地点（线上）：腾讯会议ID：311 5293 0003

摘要：

I will mainly talk about our study on efficient constructions of linear and affine codes for insdel distance.  Linear codes that can correct even a single deletion are limited to have information rate at most 1/2 (achieved by the trivial 2-fold repetition code). Previously, it was (erroneously) reported that more generally no non-trivial linear codes correcting k deletions exist, i.e., that the k+1-fold repetition codes and its rate of 1/(k+1) are basically optimal for any k. We disprove this and show the existence of binary linear codes of length n and rate just below 1/2 capable of correcting Omega(n) insertions and deletions. This identifies rate 1/2 as a sharp threshold for recovery from deletions for linear codes and reopens the quest for a better understanding of the capabilities of linear codes for correcting insertions/deletions. I can also talk about outer bounds for these codes if we have time.

主讲人简介：

Kuan Cheng is now an assistant professor of Peking University, Center on Frontiers of Computing Studies. His recent research interests mainly include coding theory and randomness in computation. Previously he worked as a postdoc at UT Austin. Prior to that he received a PhD degree from Johns Hopkins University.

邀请人：胡思煌