北京大学前沿计算研究中心理论计算日在线举办
2022年6月28日，北京大学前沿计算研究中心理论计算日在线举办。本次理论计算日邀请来自美国、以色列、新加坡、中国香港等地多位理论计算领域活跃的专家学者，介绍在算法、复杂性、编码、密码学等理论计算机科学的主要分支上的最新进展。活动由中心助理教授程宽、姜少峰、刘天任主持，通过B站和蔻享学术直播，吸引近千人观看并参与讨论。
CFCS TCS Day 讲者合集
活动伊始，中心执行主任邓小铁教授代表中心对与会嘉宾和观众表示欢迎，并介绍了中心的基本情况和发展历史。他表示，中心的一个重要的研究方向即为计算理论，他期待今天该领域内的优秀学者在一起交流和研讨，碰撞出新的火花。
邓小铁教授开幕致辞
UC San Diego 的 Shachar Lovett 介绍了他在布尔函数分析的研究中的若干最新进展。报告主要围绕布尔函数的单项式表示复杂度展开。这一测度主要衡量一个布尔函数可以用多少个单项式的线性组合表示。Shachar 首先详细介绍了其定义本身以及相关的数学特性。之后与布尔函数其它测度，例如决策树深度等做了对比和联系。同时也展示了该问题同 log-rank conjecture 以及 union-closed conjecture 的密切关联。最后 Shachar 介绍了他在该方面研究的最新进展。他们发现任何布尔函数的单项式构成的集合系统具有一个较小的 hitting set。这一性质深入刻画了单项式表示的内在特性，有着广泛的应用。随后他还介绍了部分证明技巧的细节。
The Monomial Structure of Boolean Functions
MIT 的陈立杰从最优假设与时间膨胀两个方面介绍了去随机化的最新进展。既有的去随机化研究中，考虑的假设或者强于去随机化，或者弱于去随机化。陈立杰引入了首个对于去随机化充分必要的假设类型。构造新的去随机化方法，使得时间膨胀约等于输入长度，这对于黑盒去随机化来说是最优的（假设 NSETH）。同时还开展了“非黑盒”的去随机化研究，在允许难以发现的错误放入前提下，近乎消除了去随机化的时间膨胀。
Recent Developments in Derandomization
北京大学前沿计算研究中心的姜少峰聚焦于高维欧式空间，研究了设施选址数据流算法。具体地，姜少峰团队提出了一种全新的几何哈希方法，并利用此方法提出了一个基于重要性采样的算法框架。在 two pass 和 random order 数据流模型中，算法均只需要 poly(d·log△)空间即可得到常数近似比的解（假定数据在[△]d的 d 维离散网格上）；对于 one pass 数据流，算法也用poly(d·log△)空间达到了O(d1.5)近似比，改进了先前 Indyk 等人的针对高维空间的O(d·log2△)近似比。
Streaming Facility Location in High Dimension
北京大学前沿计算中心的程宽介绍了他在编码理论领域的最新成果。报告系统展示了局部可解码编码的研究历史、主要结论，以及当前主要的未知问题。所展示的最新成果集中于编辑距离局部可解码编码方面。该方向是近期的热点研究方向。其最新研究成果给出了此类编码的指数级和无穷级下界。这些成果均强于以往的已知的结果，其中的无穷级下界结论是该研究中首次发现的。该报告详细展示了所采用的新方法，对集中、反集中特性、光滑性特性等主要方法的思路进行了详细阐述。
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletion
北京大学前沿计算研究中心的刘天任从 t-wise 独立性的角度，研究常用加密算法框架的安全性，其中涵盖了最广为使用的 AES 算法。简要来说，证明了 AES 满足 2-wise 独立性。即任选两个明文，用 AES 加密得到的两个对应密文近似服从独立均匀分布。这说明 AES 算法能够抵抗差分攻击等常见攻击手段。从理论角度分析，刘天任还证明 KAC（AES 是其特例）只需要大约 t 轮，就近似满足 t-wise 独立性。
The t-wise Independence of Substitution-Permutation Networks
新加坡国立大学的 Diptarka Chakraborty 介绍了关于聚合任务研究的最新进展。具体地，Diptarka 首先介绍了当数据点是字符串时，在编辑距离下的聚类问题、数据集代表点（如 median、center）的计算问题，并且综述了相关（近似）算法以及目前所面对的开放问题；随后，Diptarka 引出一种特殊情形，即总结了当数据点是 [n] 的排列时，在 Ulam 距离下的研究进展。
Aggregating a Data Set: Rankings to Strings
以色列 Ben-Gurion 大学的 Dean Doron 介绍了针对 BPL 去随机化问题的研究现状以及他在该方面研究的新进展。Dean 首先回顾了该问题30多年来的研究历史，详细介绍了 Nisan's PRG，INW PRG，Saks and Zhou 去随机化等经典方法，之后介绍了伪随机分布、Laplacian Solver 等新技术，以及他对 Saks and Zhou 去随机化方法的改进。该改进在某些设定下就有明显的复杂性优势。同时他也介绍了目前对该方向研究的新视角，例如寻找更多可以在对数空间复杂度内确定性可解决的问题等。
Recent Progress on Space-bounded Derandomization
香港中文大学的 Andrej Bogdanov 介绍了他在密码学与伪随机研究方面的最新进展。该报告主要关注如何运用零知识证明进行伪随机分布区分。这一思路与常规方法有多个显著区别，利用零知识证明使得这里的区分器显著强于常规概率多项式时间算法，其处理的对象分布来自于 NP 中的某些困难但相信并非是 NP 完全的问题。他着重介绍了若干距离实例，以及 rerandomness 等技巧，用新颖的视角和方法在密码学和复杂性研究领域开拓了新方向。
On Breaking Encryption with a Statistical Zero-knowledge Oracle
以色列 Tel-Aviv 大学的 Benny Applebaum 介绍了安全多方计算领域的前沿成果，特别是信息论安全（即不依赖任何算力假设）的多方安全计算协议。近年在这个领域中，一个称为二次多方随机化编码（2MPRE）的工具展露头角。此前的 2MPRE 都需要假设大部分参与者是诚实的。Benny 新构造的 2MPRE 可以在只需要三分之一的参与者诚实。Benny 还揭示了 2MPRE 与 OT-hybrid 多方计算模型之间的联系。
Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
以色列 Tel-Aviv 大学的 Uri Stemmer 介绍了在数据流中，对经典 CountSketch 数据结构在 k heavy hitters 任务中的鲁棒性的研究结果。具体来说，该工作考虑输入可以取决于之前所有输入以及算法输出的情形下的算法的鲁棒性（即相对于经典的、输入不取决于算法输出的模型下的性能）。Uri 的报告阐述了两个主要结果：首先 Uri 指出 CountSketch 本身不具备良好的鲁棒性，并且提供了一种攻击方法；之后，他给出了一种基于差分隐私的 CountSketch 的变体，且相比于先前的工作，他们的方法在保证鲁棒性的同时，还优化了空间复杂度。
On the Robustness of CountSketch to Adaptive Inputs