FOCS 2021 | 针对Insdel间隔的局部可解码编码的下界

近日,北京大学前沿计较研讨中心助理教授程宽博士与其合作者的论文“Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions”发表在理论计较机科学国际顶级会议 FOCS 2021上。这篇文章探讨了编码理论中的一个重要课题,Locally Decodable Code 在 insertion deletion distance 场景下的下界。

FOCS 2021 | 针对Insdel间隔的局部可解码编码的下界

编码理论研讨的是各种编码的性子及其应用。传统意义上的编码,是指把某个信息空间映照到某个具有普通性子的度量空间。原空间的每个元素被称之为信息,映照后得到的对象被称之为 codeword。一类最常见的普通性子是纠错性子,也就是 codewords 之间的间隔相对较远,这样的话,当发生在 codeword 上的谬误量不超过间隔的一半时,就还是可以恢复出正确的 codeword。

Locally Decodable Code (LDC) 是一种普通的纠错码,它的纠错算法就有局部访问特性,就是在指定肆意一个信息比特之后,该算法可以通过仅仅访问“codeword”中的少量比特就能恢复事先指定的肆意一个信息比特。

计较下界是理论计较机科学常见的研讨目标之一。通俗来讲就是研讨给定的计较模型或计较方式解决不了什么样的课题。与之相对的是计较上界,一般的含意就是什么样的课题可以被(有效)解决。具体来说,这篇新处事研讨的是什么样参数的 LDC 是不可能存在的。关于这里的参数,之前的研讨最关注的一般是冗余度,就是信息长度和编码长度的比例。

该课题针对汉明间隔 LDC 的版本已经在过去几十年中被充分研讨了,这些研讨的主要目标了解想要在大量谬误和较少查询的情况下解码,多少冗余度是必要的或足够的。前面给出的冗余度一般是指数级的。这意味着,即使最好的汉明间隔 LDC,它的编码长度也必须是信息长度的指数,即冗余度很大。

FOCS 2021 | 针对Insdel间隔的局部可解码编码的下界

这篇新的处事研讨的是针对 insertion deletion (insdel) 的 LDC。Insdel 的含意是指谬误类型包括插入字符和删除字符。该研讨最初由 Ostrovsky 和 Paskin-Cherniavsky 开始,它们的格式是构建从汉明 LDC 到 Insdel LDC 的归约。而新处事则给出了一个新的证明格式,并且给出了 Insdel LDC 的更强的计较下界。一是 2-query insdel LDC 只能支持常数个信息比特,二是所有 q-query insdel LDC 都有指数级的下界,q 是肆意常数。这些下界比针对汉明间隔的 LDC 的下界要明显更强。比如 2-query 的情况,新处事的结论意味着,无论如何结构 LDC,不管编码长度设置成多长,哪怕是任何的超越指数这种级别,其信息量也只能是常数个比特。另外简单思考一下不难看出,只含有常数个信息比特的 Insdel LDC 是很容易结构的,大量重复信息比特即可。这也就意味之我们给出的计较下界已经基本匹配了该课题的计较上界,形成了对该课题研讨的比较完整的刻画。

新处事在格式上的主要创新是结构了一些精巧的普通 insdel 分布(如图中所示),并分析了这种分布对 insdel LDC 的影响。FOCS 2021 | 针对Insdel间隔的局部可解码编码的下界

该论文与普渡大学的 Jeremiah Blocki, Elena Grigorescu, Minshen Zhu 以及约翰斯霍普金斯大学的 Xin Li, Yu Zheng 合作完成。该处事得到了北京大学引进人才启动经费和北京大学信息技术高等研讨院的经费支持。

图文 | 程宽

原创文章,作者:北京大学前沿计算研究中心,如若转载,请注明出处:https://www.iaiol.com/news/focs2021-zhen-dui-insdel-jian-ge-de-ju-bu-ke-jie-ma-bian-ma/

(0)
上一篇 2022年 7月 18日 下午5:04
下一篇 2022年 7月 18日 下午5:06

相关推荐

  • 深度进修模型知识产权损坏怎么做?看看IJCAI 2021这场Workshop说了什么

    在刚刚结束的 IJCAI 2021 大会上,「深度进修模型知识产权损坏国际研讨会(DeepIPR-IJCAI’21)」正式举行,这场研讨会由微众银行、马来亚大学、香港科技大学、上海交通大学共同主办。

    2021年 8月 31日
  • 千字1.5元、研究生学位论文3次收费,知网凋谢集体查重办事,网友:「卒业了才凋谢」

    不过,对于 2022 届的卒业生来说,知网的这一决定来得似乎晚了一点。

    2022年 6月 12日
  • 华夏华文信息学会2020学术年会& “钱伟长华文信息处置科学技术奖”颁奖大会在京召开

    2020年12月27日, 华夏华文信息学会2020学术年会在北京隆重举行,会上颁发了“钱伟长华文信息处置科学技术奖”,华夏华文信息学会“青年创新奖”,以及华夏华文信息学会“优秀博士学位论文奖”。大会邀请了5位国内著名专家做特邀告诉,还邀请了6位国内资深学者进行了主题为“语言智能与信息安全”的专题研讨。来自华夏科协、教育部国家语委领导和华文信息处置范畴的专家学者参加了本次会议,哔哩哔哩平台对大会进行现场直播,线上观看人数超过3000人。华夏华文信息学会2020学术年会在北京隆重举行大会开幕式及领导致辞大会开幕式由华夏

    2020年 12月 29日
  • 为主动驾驭汽车创造「影象」,上交校友、康奈尔大学博士生两篇论文被CVPR 2022收录

    人经常走一条路能走熟,主动驾驭汽车也应该能。

    2022年 7月 14日
  • 用技术致敬每一位妈妈,B站up主用AI复原李焕英老照片动态影像

    「从我有记忆开始,妈妈就是中年妇女的模样,所以我会忘记,她也曾是花季少女。」

    2021年 2月 23日
  • 现在入行CV还有前途吗?AI青年学者这样看「未来五年的计算机视觉」

    为了推动 AI 技巧的应用创新,促进人工智能范围的学术交流、人才培养,打造人工智能的人才交流平台与产业生态圈,中国人工智能学会联合杭州市余杭区人民政府联合发起了首届全球人工智能技巧创新大赛,并得到了阿里云、OPPO 等头部科技企业的积极参与和支持。阿里云天池平台为本次大赛提供平台和算力支撑。

    AI 青年说是大赛主办方为提升青年开发者对 AI 的认识而主办的系列活动,该活动邀请知名青年学者,探讨理论研究与应用实践中的热点话题。本文对 AI 青年说系列活动第三期「未来五年的计算机视觉」核心内容进行了总结回顾。

    2021年 4月 30日
  • DeepMind联合UCL,推出2021加强进修最新课程

    DeepMind 的研讨科学家和工程师亲身讲授了一套加强进修课程,目前已全部上线。DeepMind 作为全球顶级 AI 研讨机构,自 2010 年创建以来已有多项世界瞩目的研讨成果,例如击败世界顶级围棋玩家的 AlphaGo 和今年高效展望的蛋白质结构的 AlphaFold。近几年,DeepMind 联合伦敦大学学院(UCL)推出了一些人工智能线上课程,今年他们联合推出的「2021 加强进修系列课程」现已全部上线。该课程由 DeepMind 的研讨科学家和工程师亲身讲授,旨在为学生提供对现代加强进修的全面介绍。课程

    2021年 9月 16日
  • 周志华、李航、邱锡鹏、李沐、Aston Zhang 5位专家指导,机械之心发布ML术语中英对照词表

    几年前机械之心发布了一个旨在构建 AI 范围术语库的开源项目「Artificial-Intelligence-Terminology-Database」(简称「AITD」)。最近,该项目迎来了第三版。除了常规的更新之外,机械之心还在周志华教授、李航博士、邱锡鹏教授、李沐博士、Aston Zhang 博士等范围专家的指导及帮助下形成了「机械进修」专题篇。未来,机械之心还将会持续完善术语的收录和扩展阅读的构建,另外我们也希望更多 AI 技术社区成员参与到术语库的构建之中,具体的参与方式可以查看文章详情。2017 年,机

    2021年 8月 19日
  • 读博五年,我总结出了7条帮你「少走弯路」的真理

    这些经验教训不一定有关学术,但长远来看,将有益于你所接触的任何歇息。

    2021年 12月 31日
  • 94岁诺奖得主希格斯去世,曾预言「上帝粒子」的消失

    一名用诗意的语言揭示宇宙秘密的人。一名 94 岁巨大科学家的逝世,引发了人们广泛的哀思。4 月 10 日消息,诺贝尔物理学奖得主、著名物理学家彼得・希格斯(Peter Higgs)于周一去世,享年 94 岁。希格斯因提出希格斯玻色子也被称为「上帝粒子」而闻名。根据爱丁堡大学的一份声明我们得知(彼得・希格斯是该校的光荣退休传授),希格斯经历短暂的生病后,于 4 月 8 日星期一在家中安静的离开。对于老爷子的去世,爱丁堡大黉舍长 Peter Mathieson 沉重的表示:「彼得・希格斯是一名杰出的科学家 &mdash

    2024年 4月 10日

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注