编者按

2020年，前沿计算研究中心还迎来了一位理论计算方向的新体制助理教授：程宽。低调的他相信行胜于言，不过在聊起他感兴趣的问题时常会侃侃而谈。

      程宽，2019年于约翰斯霍普金斯大学获得计算机科学博士学位，之后在德克萨斯大学奥斯汀分校从事博士后研究工作，于2020年8月加入北京大学前沿计算研究中心，任助理教授、博士生导师。他的研究方向是计算模型与复杂性，主要包括计算中的随机性，编码理论，机器学习理论等。

问：可否描述一下你对理论计算机科学的认识？

程宽：我认为这个领域主要研究各种计算模型以及他们对各种问题的解决能力。最常见的计算模型是传统的图灵模型，可以把它想象成一台电脑，使用一定的时间和空间，串行解决某些问题。

      计算模型的种类是丰富多彩的，有多种多样的计算方式和计算资源。比如，计算方式上可以串行，也可以并行；可以用自动机模型，也可以直接用电路模型；可以与外界进行通信，也可以扔硬币碰运气，还可以动用量子比特。一些抽象的计算模型甚至还可以展开多个平行世界进行计算，或者直接向某些更强的计算参与者询问答案。还有的时候可以拿尚不知道答案的某些问题来解决其它问题，比如现代密码学中用到的各种假设。

问：你研究领域中的主要问题有哪些？

程宽：我从博士开始就对计算中的随机性和编码理论很感兴趣，一直在围绕这个主题展开工作。首先是计算中的随机性。主要研究随机算法可以解决什么样的问题，以及什么样的随机算法可以被去随机化。具体的例子包括，如何设计高效的随机采样算法，以及如何缩小它的样本空间。然后是与随机性相关的编码理论。例如，如何用随机算法构造功能更强大的纠错码。做这些研究是为了搞清楚相关计算模型的计算能力。我想，这也正是人们研究计算机科学的根本原因之一。

      此外，这些理论研究在一些关键的应用领域也扮演了重要角色，例如，编码理论和实际运用的通信算法就紧密关联，像目前在5G通信中有着广泛应用的 Polar code，LDPC code 等等。从更高的层面来讲，我认为理论研究的一个重要意义是准确预见未知领域，减免实践代价，它与实际应用是相辅相成的。

问：你之前在约翰霍普金斯大学（Johns Hopkins）和德克萨斯大学奥斯汀分校（UT Austin）时做的主要工作有哪些？

程宽：在 Johns Hopkins 时，我主要做了两部分工作。首先是给出了 Randomness extraction 的常数层电路计算算法。这个算法的主要作用是把一些并不均匀分布的随机比特转变成均匀分布的比特串。实际上它也是一个常数层电路可计算的随机采样算法。它的一个直接 implication 就是可以用更少的随机比特来大幅提升常数层电路随机算法的判定成功率。相关工作发表在 Random/Approx 2018。

      另一部分工作是研究编辑距离编码的相关问题，具体是利用随机和去随机化的方法给出了目前二进制最好的编辑距离 Document Exchange 协议和编码。简单来讲，就是假设有两个通信方各有一个字符串，两个串有一定的编辑距离，如何让通信双方用最少的交流来得到对方的输入字符串。相关工作发表在 FOCS 2018，SODA 2019，ICALP 2019。

      在 UT Austin 时，我主要研究了如何利用 Hitting Set Generator 对 BPL 进行去随机化的问题。这个问题的大背景是如何对小空间随机算法进行去随机化。很多研究者相信这些算法是可以完全去随机化的，却一直未能解决这一问题。我们的工作是对这个方向的一个小贡献。相关工作发表在 CCC 2020。

问：可否介绍一下你近期的工作？

程宽：2021年1月，我们有两个工作在 SODA 2021*上发表，都是关于编码理论的。第一篇文章研究的问题是，如何使用最小的通信复杂度使得通信双方了解自己的输入字符串与对方的输入字符串有何不同。我们侧重于处理通信双方信息不对称的情况。我们给出了针对这一问题的高效通信算法，并且在经典解码算法“Belief Propagaion”的基础上研发了“Belief Propagation with restrictions”，作为通信中接收方算法的重要组成部分。通过该算法的名字就可以看出这是一个机器学习类型的算法，但和传统机器学习算法相比较，它是为数不多的既可以证明正确性又很高效的算法。最后，我们还利用了这些结果去优化了相应的对称情况下的算法。

      第二篇文章主要是研究针对编辑距离的线性纠错码。这种编码主要是指高维空间的一种离散子集，它当中任意两个点之间的距离都足够大。常见的应用是通信中的信息纠错，因此也叫纠错码。与以往的编辑距离纠错码不同的是，我们给出的构造具有线性空间特性，并同时有较高的纠错率和信息率。线性空间特性是一种比较强的代数特性，我们相信这种特性将在编辑距离纠错码的一些应用场景中发挥作用。

*离散算法国际研讨会（ACM-SIAM Symposium on Discrete Algorithms, SODA）由计算机协会（ACM）和工业与应用数学学会（SIAM）两大国际学术组织联合主办，与 STOC、FOCS 一起被公认为是算法领域的三大顶级学术会议。

问：对未来的科研工作有什么规划？

程宽：计算模型与复杂性是个广阔的领域，在此之中，我主要专注于计算中的随机性及其相关的电路计算模型、通信模型的研究。首先，我会继续对计算中的随机性以及编码理论进行钻研，特别是其中居于关键位置的课题，争取对这些传统问题建立新的更深刻的认识。同时我也打算结合目前流行的研究热点，例如人工智能、机器学习、量子计算等，进行前沿扩展研究。我会特别注重国家发展的战略需求，把这些同我以前的研究经历相结合，争取做出更多贡献。当前我看到的可以做的问题还是挺多的，也欢迎感兴趣的研究者一起来探讨。

2020年10月中心教师合影