• 学校首页
  • 办公信息
  • 邮箱
  • 网站后台
  • English

Efficient Linear and Affine Codes for Correcting Insertions/Deletions

发布日期:2021/11/26 点击量:

报告题目: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.


邀请人:胡思煌


联系我们

地址:山东省青岛市即墨区滨海路72号山东大学青岛校区淦昌苑D座邮编:266237

邮箱:cst@sdu.edu.cn电话:(86)-532-58638601传真:(86)-532-58638633

版权所有 Copyright © 山东大学网络空间安全学院