从图灵奖到雨果奖

从科学到科幻

零一字节演绎数理逻辑的缜密精妙

如椽大笔挥洒动人情节的天马行空

来静园五院与图灵班人一起

分享这份独特的深刻与浪漫

2023年6月4日 13:00

北京大学静园五院204

活动安排

　　1. Designing Programs that Check Their Work---Manual Blum

　　如何知道一个程序对于一组输入输出是否是正确的？对于这个问题，Manual Blum 设计了一些有趣的机制，通过构造一些问题来让程序"自相矛盾”。这个问题富含着一种生活智慧，或许能让我们在日常生活中更能明辨是非吧~

　　
——分享者：冯施源

　　2. Should Tables be Sorted?---Andrew Yao

　　选择姚先生这篇论文一定程度上出于偶然，先是尝试性地选择了姚期智先生这位唯一获图灵奖的华人学者，然后在 ACM 网站上浏览对他的介绍时看到了 ”Should Tables Be Sorted?“ 这篇写于1981年论文，被这个质朴而有趣的发问吸引。的确，tables 是再熟悉不过的最基础的数据结构之一，我习惯性的认为从小到大排好序的事物是更好处理的，却从来没想过，果真如此吗？有没有更有趣而高效的结构？这篇文章给予了我对这个话题更多深入而有趣的思考。

　　
——分享者：吴悦天

　　3. The Complexity of Computing the Permanent---Leslie Valiant

　　有 OI 背景的同学对计数题应该并不陌生。Leslie G. Valiant 的这篇论文从计算复杂性角度探讨了计算积和式的“困难性”，并在之后的工作证明了很多计数问题之间的联系，为 #P 的研究打下了基础。

　　
——分享者：彭博

　　4. The Knowledge Complexity of Interactive Proof-System---Silvio Micali

　　在做数独时，“数独有解”所蕴含的信息比“数独的解中每个位置的数字”要少；在计算问题时，“结果是真”所蕴含的信息比“给出解为真的证明”要少。而在实际问题中，我们未必希望为对方传递太多信息，例如让对方相信我能求出答案的同时不向对方透露任何答案以外的信息。这里就引入了“知识复杂性”和“零知识证明”的概念。

　　《交互证明系统中的知识复杂性》在研究这个密码学问题中，给出了“零知识证明”的定义，这个定义为后来密码学的研究带来的深远的影响，如多方安全计算等。另外，零知识证明加深了人们对交互证明系统的理解，使得零知识证明系统推动了计算复杂性领域的发展。

　　
——分享者：吴天意

　　5. Performance, Design, and Autotuning of Batched GEMM for GPUs---Jack Dongarra

　　计算两个矩阵相乘，是机器学习和神经网络中十分重要的一环。当你编程解决这个问题时，是否还在使用3个 for 循环？当你调用库函数或是重载的乘法运算符时，是否想过 GPU 是如何在短时间内完成如此多不同规模矩阵乘法计算的？经典通用矩阵乘法（GEMM）采用分块的方式对矩阵并行计算以提高 GPU 利用率，然而在面对过于“竖直”“扁平”的矩阵时将有大量GPU空置，效率仍有待提高。这篇论文提出的“batched GEMM”和“vbatched GEMM”以新的方式自动为数据调配参数，使其能够适应各种大小的矩阵而保持极好的表现，其应用于 LAPACK 和 BLAS 基础库将对高性能计算领域产生重大影响。

　　
——分享者：孙心豪

　　6. 雨果奖作品分享

　　
~敬请期待神秘嘉宾~