近日，网络空间安全学院信息安全与密码研究所邢朝平讲席教授与卡内基梅隆大学Venkatesan Guruswami教授合作在列表译码方面取得重要进展，相关论文“Optimal rate list decoding over bounded alphabets using algebraic-geometric codes”已被计算机学科顶级刊物Journal of the ACM正式接受发表。

Journal of the ACM (JACM 杂志)是中国计算机学会推荐的交叉/综合/新兴板块的A类学术期刊，主要发表在计算机科学原理方面具有持久价值的研究工作。Guruswami教授和邢朝平讲席教授撰写的论文构造了一个目前最优的列表译码，解决了列表译码研究中的一个重大挑战。

创新成果

列表译码在信息通信与信息安全领域有着重要的应用，如一条消息从发送方到接收方的信道传输过程中，由于噪声的原因，消息可能发生错误，列表译码提供了一种方法，可以纠正更多的传输错误位，从而返回一个包含所发送消息的列表。

对于具有一定纠错能力的列表译码编码，应当有更小的字母表大小和列表大小(即上图圆内码字的数目)，使得在实际中有更低的计算复杂度和高效的译码效率。然而，其字母表大小和列表大小分别遵从一个理论下界。注意到如果一个列表译码的构造越靠近这个下界，那么这个码的构造就越是优的。

但是，迄今为止，所有的列表译码的编码显示构造中，或者其字母表很大，甚至依赖于码长，或者列表很大，是码长的指数级别，与理论下界相差甚远，而构造能够达到界的优的列表译码编码依然是很困难的问题。

本论文利用代数几何码构造了两类可以高效列表译码的编码，这两类码的码表大小与理论下界相比只相差一个常数因子，几乎是最优的。另外，第一类构造中的列表大小与已有构造中最小的列表大小相当，同时，这两类编码还具有最优的纠错半径以及低的译码复杂度。这也是目前构造的最优的列表译码。

完成人

该论文完成人为：卡内基梅隆大学Venkatesan Guruswami教授和上海交通大学邢朝平讲席教授。Venkatesan Guruswami教授现任上海交通大学访问教授，根据理论计算机领域的国际惯例，该论文作者按照姓名字母顺序排列。

2019年以来，网络空间安全学院通过引育并举，快速集聚了一批高水平学术带头人和优秀青年，成立了以国际密码协会会士来学嘉、海外高层次人才邢朝平、长江学者谷大武、国家杰青刘胜利等骨干教授团队组成的信息安全与密码研究所。Guruswami访问教授、邢朝平讲席教授的这篇高质量论文也从一个侧面反映了学院在密码学和信息安全相关研究的最新成果和水平，为一流网络安全学院的学术队伍建设、人才培养和跻身世界一流做出了重要贡献。

论文链接：https://arxiv.org/abs/1708.01070