演讲人：韩永祥博士 东莞理工学院
时间：2019 年 4 月 19 日（星期四）下午 14:00-15：00
地点：张江校区第二教学楼 207 室
联系人：王新 xinw@fudan.edu.cn
摘要：
代数中的一个基本课题是减少在多项式计算的复杂性。快速傅里叶变换（FFT）作为一种有效的途径，被广泛应用于构建许多的快速和高效的多项式算法，例如 Reed-Solomon 编码的编解码过程。然而，从算法的角度来看，传统的快速傅里叶变换很难直接应用到当前常见的二值有限域算法。根据我们的调研，当前还没有在 O(h*log2(h)) 操作内，就可以完成二值有限域的傅里叶变换和多项式乘法的算法。在这个讲座中，我们展示了一个二值有限域的基准并且将其应用到了 Reed-Solomon 编码纠删编码的编解码过程。在较小首项常数值（leading constant）情况下，我们提出的多项式基准实现了在 O(h*log2(h)) 有限域运算操作下完成 h 位的多项式点乘算法。相较于 canonical 多项式基准，我们的基准将多项式的加法、乘法和确定多项式度数的确定算法复杂度从 O(h*log2(h)*log2(log2(h))) 下降到了 O(h*log2(h))。基于以上的理论，我们开发了一个 Reed-Solomon 编码的编解码算法。在编码参数 (n = 2^r; k) 时，我们的算法实现了在 O(n*log2(k)) 个有限域操作的复杂度下完成编码操作，并且在 O(n*log2(n)) 个有限域操作下完成解码操作。根据我们的调研，这是第一个纠删编码的编解码方案可以同时在加法和乘法操作上，实现 O(n*log2(n)) 的计算复杂度。对于首项常数值较小的多项式计算场景，我们提出的方案具有较好的实际应用前景。
本项研究工作已经发表在了 FOCS 2014（the 55th Annual Symposium on Foundations of Computer Science)。
报告人简介：
韩永祥博士 1984 年毕业于台湾清华大学电机工程学系并于 1986 年于同系取得硕士学位。1993 年韩博士于纽约州雪城大学获得计算机与信息科学博士。他曾于华梵人文科技学院，暨南国际大学，以及台北大学任教。从 2010 年 8 月起，他任教于台湾科技大学电机工程系并于 2011 年 6 月起荣任学校讲座教授。目前他也是东莞理工学院杰出人才特聘教授。
韩博士的研究兴趣主要是在纠错码，无线网络和信息安全。韩博士已从事最先进的纠错码译码研究超过 29 年。29 年前他首先开发了基于 A * 算法的连续型译码算法。当时，该算法吸引了大量的关注，因为它是对二进制线性分组码最有效的最大似然软判决译码算法。此译码算法已被收录于纠错码的经典教科书中。
韩博士还成功地应用编码理论于无线传感器网络的研究领域。他已出版几个关于无线传感器网络研究的高被引用著作。其中一篇关于随机密钥预分配方案著作被引用超过两千次。他还担任多个国际学术刊物的编辑。韩博士是 1994 年雪城大学博士论文奖得主，同时也是 IEEE Fellow。2013 年他的一个论文赢得了久负盛名的 ACM CCS Test of Time 奖。此奖项为 ACM 信息安全领域的年度最有影响力论文奖。
