编码理论研讨的是各种编码的性子及其应用。传统意义上的编码，是指把某个信息空间映照到某个具有额外性子的度量空间。原空间的每个元素被称之为信息，映照后得到的对象被称之为 codeword。一类最常见的额外性子是纠错性子，也就是 codewords 之间的间隔相对较远，这样的话，当发生在 codeword 上的毛病量不超过间隔的一半时，就还是可以恢复出正确的 codeword。
Locally Decodable Code (LDC) 是一种额外的纠错码，它的纠错算法就有局部访问特性，就是在指定任务一个信息比特之后，该算法可以通过仅仅访问“codeword”中的少量比特就能恢复事先指定的任务一个信息比特。
估计下界是理论估计机科学常见的研讨目标之一。通俗来讲就是研讨给定的估计模型或估计方式解决不了什么样的课题。与之相对的是估计上界，一般的含意就是什么样的课题可以被（有效）解决。具体来说，这篇新事情研讨的是什么样参数的 LDC 是不可能存在的。关于这里的参数，之前的研讨最关注的一般是冗余度，就是信息长度和编码长度的比例。
该课题针对汉明间隔 LDC 的版本已经在过去几十年中被充分研讨了，这些研讨的主要目标了解想要在大量毛病和较少查询的情况下解码，多少冗余度是必要的或足够的。前面给出的冗余度一般是指数级的。这意味着，即使最好的汉明间隔 LDC，它的编码长度也必须是信息长度的指数，即冗余度很大。
这篇新的事情研讨的是针对 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 的影响。
该论文与普渡大学的 Jeremiah Blocki, Elena Grigorescu, Minshen Zhu 以及约翰斯霍普金斯大学的 Xin Li, Yu Zheng 合作完成。该事情得到了北京大学引进人才启动经费和北京大学信息技术高等研讨院的经费支持。
图文 | 程宽