本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来席浩诚同学和熊诺亚同学的报告。两场报告分别与高效深度学习和低秩矩阵复原相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  席浩诚是姚班2020级本科生，研究方向为Efficient Machine Learning。本次Seminar他将主要介绍他在上学期在清华关于low-bit quantized training的工作Jetfire。预训练transformers通常非常耗时并且耗显存。全量化训练（Fully Quantized Training，FQT）是加速预训练的一种有希望的方法。然而，大多数FQT方法采用量化-计算-反量化的过程，这往往会导致变换器的速度优化不佳，性能显著降低，原因是高内存访问开销和低精度计算。在这项工作中，他们提出了Jetfire，一种针对transformer的高效准确INT8训练方法。他们提出使用INT8数据流来优化内存访问，并采用逐块量化方法来保持预训练变换器的准确性。广泛的实验证明，Jetfire方法达到了与FP16训练基线相当的准确性，并且相比FP16基线提供了1.42倍的端到端训练加速和1.49倍的内存减少。这项工作目前在投于ICML 2024，论文的详细内容参见https://arxiv.org/abs/2403.12422

• 报告 2 摘要

  熊诺亚是姚班 2020 级（计科01）本科生。本次 seminar 他将介绍他在华盛顿大学杜少雷老师（Simon Shaolei Du）课题组春研期间关于低秩矩阵复原的工作。以往的研究经常观察到过参数化往往会显著地减速低秩矩阵复原问题中梯度下降的收敛。在这段研究中，我们给予了这一现象的理论刻画：(1). 对于对称矩阵复原问题，过参数化会导致梯度下降的收敛速率从线性减慢到多项式收敛。(2). 对于非对称矩阵复原问题，我们发现梯度下降仍然拥有线性的收敛速率，并且阐述了梯度下降的减速幅度与矩阵初始化的大小之间的关系。最后，基于理论的证明思路，我们提出了一个能够将收敛速度恢复至线性（且与初始化无关）的加速方法。相较于之前的加速方法，我们的算法只需要在梯度下降收敛到邻域后进行一步修改，在计算复杂度上有着显著改善。此工作发表于ICLR 2024，并入选焦点论文。论文链接：https://arxiv.org/pdf/2310.01769.

欢迎全体同学参加~

本周六晚上 20:30 - 21:30，我们将在学堂 112【线下】给大家带来吕凯风老师关于深度学习理论的报告。在报告前后，同学们可以吃零食 and/or 自由交流。

• 报告摘要

  吕凯风即将于 2025 年入职交叉信息研究院任助理教授。他于 2019 年毕业于姚班，博士就读于普林斯顿大学。随着深度学习模型越来越大，能力日益增强，如何降低训练成本及确保人工智能的安全性，已经成为两个至关重要的问题。然而，我们究竟了解神经网络在学习什么，以及它是如何进行泛化的吗？本次 seminar，吕凯风会介绍一些近期的研究成果，从理论和实验的角度探究以下问题：(1) 在大规模分布式训练中，降低梯度信息的同步频率能节省通信成本，也会导致训练偏离梯度下降的路径。但模型的泛化表现却神奇地变好了，这是为什么？(2) 对一个 safety-aligned 的语言模型稍作微调，哪怕是在一个看似无害的数据集上，也可能改变其在安全性方面的泛化表现，使其更易于被恶意用户利用来危害社会。我们应如何缓解这一问题？

欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来徐翊轩同学和陈昱蓉学姐的报告。两场报告均与博弈论相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  徐翊轩是姚班 2020 级（计科02）本科生，他主要的研究方向是博弈论和计算经济学。本次 seminar 他将介绍他在卡内基梅隆大学春研期间关于 Learning in Games 的工作。在各种现实世界的多智能体系统中，智能体之间结盟的现象 (Coalitions) 普遍存在。例如，在拍卖系统中，竞拍者可能会组成联盟，在私下协调他们的出价，以利用拍卖机制，增加他们总体获胜的机会。对于这些多智能体系统的设计者来说，智能体之间的联盟结构 (Coalition Structures) 往往是未知的，而得知联盟结构却会为平台监管、机制设计提供方便。由此，本篇工作提出并研究了联盟结构学习 (Coalition Structure Learning) 问题。在这个问题中，我们需要设计一种算法来学习多智能体系统中客观存在，但对于算法来说未知的联盟结构。这里，算法扮演系统设计者的角色，具有为系统中的智能体设计少量博弈和观察这些博弈结果的能力。根据系统中客观存在的联盟结构，智能体可能在博弈中表现出不同的行为，因此，算法可以利用观察到的结果来推断联盟结构的有关信息。本次讲座将介绍这一问题框架下的已有成果、近期进展，以及开放性问题。

• 报告 2 摘要

  陈昱蓉是北京大学前沿计算研究中心19级博士生，研究兴趣为机器学习与博弈论的交叉。虽然传统博弈论通常假设博弈参数部分或全部已知，或有一定的信息结构假设，然而，在现实中，这些参数往往难以直接确定，比如，效用函数通常为玩家自己的私有信息。尽管机器学习可以从数据与交互中学习这些参数，但理性的博弈玩家可以利用他们的私有信息优势，在与学习算法的交互中博弈获利。为了将机器学习和博弈论更稳健地应用于实践中，研究如何学习私有信息以及智能体如何利用其信息优势至关重要。此次报告将介绍她关于私有信息学习与操纵的一系列工作。

欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来温凯越同学和刘益枫同学的报告。两场报告分别与深度学习理论和 AI4Science 相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  温凯越是姚班2020级（计科01）本科生，他的主要研究方向是深度学习理论和自然语言处理。在本次Seminar中他将介绍近期神经网络表示理论方面的一些进展。近期，Mamba和RWKV等线性RNNs，在自然语言处理任务上取得了较大进展，然而这些问题在下游任务中仍然与Transformers有较大差距。本次介绍的工作旨在探索这一现象的原因，集中评估了以内存效率著称的RNNs，能否通过适当的增强达到Transformers解决逻辑推理问题的性能水平。理论分析显示，虽然思维链技术（Chain of Thought）可以提升RNNs的性能，但仍无法弥补与Transformers之间的差距。他们指出RNNs在完美检索上下文信息方面存在关键瓶颈，即便在引入CoT的情况下，对于某些显式或隐式要求此能力的任务，如关联回忆和判定图是否为树结构，RNNs的表达力仍不足以解决这些问题，而Transformers却可以轻松完成。另一方面，通过增强RNNs上下文检索能力的技术，包括检索增强生成（Retrieval-Augmented Generation, RAG）和增加单个Transformer层，可以使RNNs具备模拟所有多项式时间图灵机的能力，从而在表示上与Transformers持平。本次Seminar也将讨论这一理论观察在一些近期实验工作中的验证。论文链接：arxiv.org/abs/2402.18510，个人主页：wenkaiyue.com

• 报告 2 摘要

  刘益枫是姚班2020级（计科03）本科生，他的主要研究方向是自然语言处理和AI4Science。本次seminar他将带来关于大语言模型在科学探索中的应用：基于大语言模型的逆合成预测。作为计算化学中的一项基本任务，逆向合成预测旨在识别一组反应物来合成目标分子。之前的无模板方法只考虑目标分子的图结构，通常不能很好地推广到稀有反应类型和大分子。刘益枫和华盛顿大学的其他研究者提出了一种文本辅助逆转录合成预测方法，利用预先训练的文本语言模型，如ChatGPT，来帮助生成反应物。 T-Rex首先利用ChatGPT生成目标分子的描述，并根据描述和分子图对候选反应中心进行排名，通过查询每种反应物的描述对这些候选者进行重新排序，确定合成目标分子的最佳反应物。 T-Rex在两个数据集上的表现明显优于基于图的其他方法，表明了文本信息在逆合成预测中具有促进作用。总的来说，由预先训练的语言模型生成的文本可以显著改善逆合成预测，为利用ChatGPT来推进计算化学开辟了新的途径。 个人主页：https://lauyikfung.github.io/

  欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来袁樱同学和张焯扬同学的报告。两场报告分别与机器人学和计算机视觉相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  袁樱是姚班2020级本科生，研究兴趣是机器人学习，将基于学习的方法用到机器人领域。本次Seminar她将介绍她在UCSD春研期间关于灵巧手操作(Dexterous Manipulation)的工作。早期的灵巧手操作方法基于传统控制理论，但这对于人为建立的动力学模型有很大程度上的依赖。该项工作围绕基于深度无模型强化学习的灵巧手操作展开，使用模仿学习、视触觉的多模态感知等方式，使得智能体习得更真实自然的操作行为，提高操作的准确性和效率。

• 报告 2 摘要

  张焯扬是姚班2020级本科生，研究方向为Efficient Machine Learning和Computer Vision。本次Seminar他将主要介绍他在UC San Diego暑研期间关于3D Generation的工作One-2-3-45++。图像生成模型如Stable Diffusion, Midjourney的成功离不开海量数据的支持，而目前3D数据相比于2D数据体量十分有限，仅使用现有3D数据训练难以获得开放世界中的生成能力。在这项工作中我们介绍了如何利用图像生成模型中学习到的开放世界的先验知识来赋能3D生成。One-2-3-45++可以在一分钟内根据单张图片/文本提示生成高质量几何，高保真纹理的3D Mesh。此工作发表于CVPR2024，相关研究成果转化为3D startup SUDOAI，欢迎大家体验demo: https://www.sudo.ai/。与此同时，他还将简要介绍近期的新工作EfficientViT-SAM，在不损失零样本分割性能的情况下相对于Segment Anything Model加速48.9倍，推动了SAM在数据标注以及实时交互场景中的部署与应用，欢迎大家体验demo: https://evitsam.hanlab.ai/。

  欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来杨骏昭同学和谭亦钦学长的报告。两场报告分别与 Parallelizing Boosting 和潜在一致性模型（LCM）相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  杨骏昭是姚班2020级本科生，研究兴趣是理论计算机科学，近期研究的问题包括计算学习理论，伪随机性和差分隐私。本次Seminar他将介绍他在UC Berkeley春研期间关于Parallelizing Boosting的工作。Boosting是机器学习中的一种集成学习方法，理论上可以将任何比随机猜测好一点的“弱学习器”（例如准确率为51%）转化为任意高准确率的“强学习器”（例如准确率为99%)，在理论和实践中都有着重要意义。然而，已知的Boosting算法（例如经典的AdaBoost算法）都是适应性的（adaptive），每一次询问弱学习器都需要依赖于上一次的回答，所以无法使用并行加速。该项工作从理论上研究了Boosting算法的并行复杂度，说明AdaBoost的询问轮数是（几乎）最优的，任何“微小”的并行加速都需要指数多的询问次数。

• 报告 2 摘要

  谭亦钦是叉院2022级硕士生。本次Seminar他将介绍关于潜在一致性模型（LCM）的研究。LCM是一种新型生成模型，具有依据文本迅速生成图片的能力。近来，扩散模型在文本至图像生成任务上展现出惊人的能力，但其基于多次神经网络推理的采样过程导致生成速度较慢，成为生成模型领域的一大挑战。受到简单图片生成任务上一致性模型（CM）的成功启发，谭亦钦与叉院的其他研究者合作提出使用潜在一致性模型来替代传统扩散模型。LCM旨在直接预测潜在空间中增强概率流常微分方程（PF-ODE）的解，从而减少迭代次数并允许快速、高保真度的采样。LCM的高效性得益于从预训练的无分类器引导扩散模型中提炼而来，一个高质量的768 x 768分辨率的LCM只需32个A100 GPU小时即可训练完成。此外，研究还引入了针对定制化图像数据集的潜在一致性微调（LCF）方法。在LAION-5B-Aesthetics数据集上的评估显示，LCM在几步推理内实现了最先进的文本至图像生成性能。

  欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来周任飞同学和李恬教授的报告。两场报告分别与数据结构和机器学习相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  周任飞是姚班2020级（计科02）本科生，他的主要研究方向是数据结构与矩阵乘法，曾在理论计算机科学顶级会议FOCS/SODA上发表五篇论文。本次seminar他将带来关于空间高效数据结构（space-efficient data structures）的教程讲座（tutorial session）。数据结构研究如何高效存储数据以便快速修改与查询信息，是整个计算机科学中历史最悠久的话题之一。空间高效数据结构作为一个子领域，研究如何在不牺牲时间效率的前提下将空间使用量压缩到极致，在理论和实践两方面均有重大意义：理论中，它揭示通讯（communication）与计算（computation）的内在联系；实践中，它帮助数据库、网络、计算生物学等多个领域节约成本。本教程面向零基础的同学，旨在通俗易懂地介绍空间高效数据结构的核心思维方式，以及一些最基础的问题与技巧。

• 报告 2 摘要

  李恬教授是Meta FAIR Labs的博士后研究员，并将在2024年入职芝加哥大学的助理教授。她博士毕业于卡耐基梅隆大学，研究兴趣包括分布式优化，联邦学习，可信机器学习，特别是principled and scalable approaches for learning across diverse data sources。为了构建合理的数据经济并保护数据隐私，从分散且异质的数据源中不加以集中地进行训练是关键所在。联邦学习的目标就是通过以网络连接的大量设备乃至独立的组织在保留数据在本地的情况下完成训练。然而联邦网络会带来许多独特的挑战，诸如过高的通讯负担，隐私约束，数据与系统的异质性等等。通过由联邦学习应用中获取的灵感，李恬教授的工作致力于提出严格的方法来完成异质网络中可扩展、可信的学习。她将论述异质性如何影响优化，以及为何会成为正确性，可信性的关键。她也会讨论可信性的目标函数以及联邦学习以外普遍的机器学习问题的优化方式。在最后，她会展望在优化与保护隐私的机器学习上的研究计划。个人主页：https://www.cs.cmu.edu/~litian/。

  欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来张涵瑞学长和郑舒冉学姐的报告。学长和学姐的报告均与经济与计算相关。在两场报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  张涵瑞是姚班2013级（计科30）毕业生，博士毕业于卡耐基梅隆大学，现为 Simons Laufer Mathematical Sciences Institute 博士后研究员。他的研究方向是（广义的）经济与计算，包括有经济学背景的学习与决策问题。本次 seminar 他将介绍关于钟表拍卖（clock auctions; cf. Milgrom and Segal, 2020）的若干结果。钟表拍卖是一种简单且有良好性质的拍卖方式。这种拍卖方式被用于2017年美国联邦通讯委员会频谱拍卖（FCC spectrum auctions），并产生了上百亿美元收入。我们将对钟表拍卖能够实现（implement）的分配函数（allocation function）进行刻画，并以此为基础探讨与钟表拍卖相关的计算问题，即价格计算与福利最大化（welfare maximization）。我们亦将探讨钟表拍卖的信息论近似能力。

• 报告 2 摘要

  郑舒冉是交叉信息研究院即将入职的助理教授。在加入清华前，她在2013-2017年就读清华姚班本科，于2017-2022年就读于哈佛大学并取得博士学位，并在之后的一年中于卡内基梅隆大学攻读博士后。本次 seminar 她将介绍她在计算经济学方向关于 Markets for Data and Information 的一些研究课题。数据是 AI 最根本的驱动力，而数据很多时候是依靠人工获得的，例如 ChatGPT 的成功就离不开大量人工标注的文本数据。近年来，数据标注已逐渐产业化，大量的平台提供数据收集和标注服务，data marketplace 的体量逐年增长。而 data marketplace 也面临着许多问题，例如最基本的：如何管控数据的质量？人们提供的数据往往难以直接验证真实性或是准确性。本次 seminar 中，她将简要介绍 data marketplace 中的两个重要话题: (1) Information elicitation: 如何设计数据评估机制，让人们提供真实准确的数据; (2) Information aggregation: 如何整合多个人提供的数据以提高准确性。

  欢迎全体同学参加~

本周六（11 月 25 日）晚上 21:00 - 22:00，我们将在建华 (经管新楼) A109【线下】给大家带来一次特殊活动：Yao Class Panel。在本次活动中，我们将召集一系列来自不同人生发展阶段嘉宾，以圆桌讨论的形式一起回答大家有关姚班学生生涯发展的问题。参与本次活动的嘉宾有：卡内基梅隆大学副教授方飞老师、清华大学交叉信息研究院助理教授张焕晨老师、普林斯顿大学在读博士生吕凯风学长、九坤 AI 算法研究员张羿翔学长、计科 02 的周任飞、徐翊轩同学。参与组织的同学将提早到达举办地点调试设备。我们推荐同学们提早半小时来到会场准备问题，并了解活动形式。

【时间】北京时间本周六 11.25 晚上 21:00 - 22:00 【地点】建华 (经管新楼) A109 【线上会议】腾讯会议 821-932-638 https://meeting.tencent.com/dm/Kjeq3aDWUFkF 【时区转换】https://www.timeanddate.com/worldclock/fixedtime.html?msg=Yao+Class+Panel+1&iso=20231125T21&p1=33&ah=1

【嘉宾简介 - 方飞】方飞老师是卡内基梅隆大学计算机学院软件与社会系统系 (S3D) 的副教授。她博士毕业于南加州大学，师从现任教于哈佛大学的 Milind Tambe 教授。她的研究领域是人工智能和多智能体系统，专注于将机器学习与博弈论相结合。她是 2022 年斯隆研究奖和 IJCAI 21 计算机与思维奖的获得者。她于 2021 年获得 NSF 职业奖，并被列入 IEEE 智能系统 2020 年“人工智能十大关注”名单。她的工作获得了 IAAI 23 部署应用奖、HCOMP 22 最佳论文荣誉提名、AAAI 21 最佳论文 Runner-up 等诸多奖项。

【嘉宾简介 - 张焕晨】张焕晨老师是交叉信息院的助理教授。他本科毕业于威斯康辛大学，博士毕业于卡耐基梅隆大学。他的研究方向是数据库系统，曾获 2018 SIGMOD Best Paper Award 和 2021 SIGMOD Jim Gray Dissertation Award。

【嘉宾简介 - 吕凯风】吕凯风学长是普林斯顿大学计算机系的博士生，师从 Sanjeev Arora。他本科就读于清华大学姚班，在此期间接受过李建老师、段然老师的指导。他将于 2025 年秋季加入清华大学交叉信息研究院 (IIIS) 担任助理教授。他在理论机器学习领域有杰出贡献，包括发表多篇论文，并担任多个国际会议和学术期刊的审稿人。此外，他还是 Yao Class Seminar 的创始人。

【嘉宾简介 - 张羿翔】张羿翔学长是九坤量化基金AI组的策略研究员。他本科就读于清华大学姚班，期间在SODA发表过一篇分布式算法领域的论文，并在2020年毕业后加入了九坤，是AI组的初创成员之一。

【嘉宾简介 - 周任飞】周任飞是交叉信息研究院计科 02 的本科生。他从事理论计算机科学研究，在数据结构和矩阵乘法领域均做出了突破性成果，在顶级会议 FOCS/SODA 上发表了 5 篇论文。

【嘉宾简介 - 徐翊轩】徐翊轩是交叉信息研究院计科 02 的本科生，从事算法博弈论研究。他的代表工作改进了应用于 Openreview 审稿平台和 AAAI 21 会议的论文 - 审稿人匹配算法，并以聚焦论文 (spotlight) 发表在 NeurIPS 23。

欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来何婉榕、陈博洋两位同学的报告。两位同学的报告分别与自然语言处理和量子神经网络相关。在两位同学报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  何婉榕是姚班2019级本科生，研究方向包括自然语言处理、人机交互和社会计算。本次seminar她将介绍她在斯坦福大学暑研期间关于建造AI系统以支持更好的网络社区环境的工作。传统社交媒体治理通常使用moderation（类似删帖、屏蔽等），但是这些方法仍无法避免网络环境的退化。在这项工作中，我们通过使用NLP模型预测策展人的偏好，首次让在社交媒体下的大规模curation（策展，类似小编精选）成为可能，并让民主、编辑精选、利益相关者圆桌等多种新型社交媒体成为可能。该文章Cura: Curation at Social Media Scale发表于The 26th ACM Conference On Computer-Supported Cooperative Work And Social Computing (CSCW 2023)并获得最佳论文奖。

• 报告 2 摘要

  陈博洋是姚班2019级本科生。本次Seminar他将介绍关于量子神经网络收敛分析的工作。量子神经网络（QNN）是一种含参量子电路，可以在近期的含噪声中等规模量子计算机（NISQ）上高效实现，与经典中基于梯度的优化器结合使用时可以用于监督学习。尽管已经有了一些经验和理论研究，QNN训练的收敛性尚未完全被理解。受到神经正切核（NTK）在探究经典神经网络动态方面的成功启发，最近的一系列研究提出通过研究过参数化的QNN来研究其量子NTK。陈博洋与马里兰大学的合作者研究了QNN的动力系统，并展示了与通常认为的随机初始化得出的NTK回归存在本质不同：由于量子操作的幺正性，存在明显的偏离正切核回归的现象。由于这种偏离，工作中证明了带有泡利测量的QNN的次线性收敛，这超出了NTK的解释能力。并且，工作中也呈现了在超参数化极限下的QNN实际动力系统。

  欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来杨景钦、骆晗两位同学的报告。两位同学的报告分别与大语言模型和密码学相关。在两位同学报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  杨景钦是姚班2017级本科生。本次Seminar他将介绍基于大语言模型（Large Language Model）的逻辑推理解决方案，并分享他与姚院士、袁洋老师合作的逻辑推理新框架。在传统思维链（CoT）和思维树（ToT）的基础上，他们提出一种“累积推理（Cumulative Reasoning）”框架，显著提升了LLMs解决复杂推理任务的准确度，特别是在逻辑推理和24点难题上实现了高达98%的准确率，在数学难题上（MATH Level 5）实现了42%的准确率相对提升。

• 报告 2 摘要

  骆晗是姚班2019级本科生、2023级直博生。在本次的Seminar中，他将为我们介绍关于量子LWE问题的研究工作。LWE问题在后量子密码学中扮演着至关重要的角色，许多密码学理论模型都可以通过它来构建。然而，LWE问题的量子版本的难度仍然存在许多未解之谜。在骆晗与他的研究团队的合作中，他们得到了以下两个成果：(1)证明了经典LWE问题可以通过量子归约转化为量子LWE问题，其中误差幅度函数包含一个未知的相位；(2)如果量子LWE问题的误差幅度函数是已知的，那么在给定次指数数量的量子LWE问题实例的情况下，存在一个次指数时间量子算法，可以解出隐藏的向量。这项工作目前在投于Eurocrypt 2024，论文的详细内容参见https://arxiv.org/abs/2310.00644。

  欢迎全体同学参加~

本周六下午 14:00 - 16:00，我们将在学堂 112【线下】给大家带来计科 01 班江昊哲、计科 03 班陈枫两位同学的报告。两位同学的报告分别与博弈论和机器人学相关。在两位同学报告之间，同学们可以吃零食 and/or 自由交流。

• 报告 1 摘要

  江昊哲是姚班2020级本科生。本次Seminar他将介绍博弈论中的机器学习问题，并具体介绍在阻塞游戏（Congestion Game）中的离线学习问题。阻塞游戏常被用于建模多智能体问题中稀缺资源的分配问题。江昊哲同研究者一起研究了如何仅利用固定数据集而不借助在线交互高效地学习阻塞游戏的纳什均衡（Nash Equilibrium），研究了相应的数据集需求，并指出了在不同反馈模型下需求的不同。该项工作 Offline Congestion Games: How Feedback Type Affects Data Coverage Requirement 发表在 ICLR 2023。

• 报告 2 摘要

  陈枫是姚班2020级本科生，研究方向主要在机器人学。本次seminar他将介绍他在麻省理工学院春研期间关于Scaling up Robotics Task的工作。近些年大模型在视觉、语言和多模态领域有了非常耀眼的突破，包括GPT-4等一系列大模型在科学研究和实际应用领域产生了卓越的突破，但是在机器人学领域，受限于数据、模型等多方面的因素，Robotics skill learning的能力依旧受限。所以在这两篇文章中，我们尝试通过引入非专家参与数据生成和自动生成两个角度进行探索，并且分别完成了一套非专家即可生成专业机器人轨迹数据的系统和自动生成轨迹数据的pipeline。第一项工作接收在Neurips 2023，第二项工作在投于ICLR 2024，同时在CoRL2023的workshop上会有相关工作的进一步讨论，https://generalist-robots.github.io/。

  欢迎全体同学参加~

本周日下午 14:00-15:30，我们将在学堂 112【线下】给大家带来计科 92 班程泽瑞、刘嘉源两位同学关于区块链的报告。两位同学的报告分别与应用密码学和机制设计相关。在两位同学报告之间，同学们可以吃零食 and/or 自由交流

• 报告1摘要

  程泽瑞是姚班2019级本科生, 研究方向包括区块链，web3和应用密码学。本次seminar他将介绍他在加州大学伯克利分校春研期间关于零知识证明跨链桥的工作。近些年来区块链系统发展迅速、热度空前，总市值超过了1万亿美元，而市面上也诞生了种类繁多的各种区块链系统，包括大家耳熟能详的比特币、以太坊等，这些区块链系统有的存储费用低、有的计算费用低、有的效率高且延时短，同时也有一些适用于特定应用场景的区块链，不同的区块链可以满足庞大用户群体的不同需求。因此，同步不同区块链上的事件，也就是跨链桥的搭建，成为了web3领域的热点问题。市面上已有的跨链桥，如PolyNetwork, Axelar, Ronin, Wormhole等，均基于委员会（committee）制度，而这一制度在恶意节点掌握大多数委员会节点时会被攻破，这也导致了最近两年经常有跨链桥被黑客攻击，造成了总计数十亿美金的资产流失。在这篇文章中，我们通过零知识证明，在保证了令人满意的效率和经济成本情况下，解决了委员会制度跨链桥引入的额外信任假设和安全危机问题，从而为跨链桥的设计提供了新的范式，从根源上加强了区块链跨链桥的安全性。从Cosmos到以太坊的单个区块证明生成和同步仅需要2分钟，且链上验真成本不到15美元。该项工作zkBridge: Trustless Cross-chain Bridges Made Practical发表于The ACM Conference on Computer and Communications Security (ACM CCS 2022)，由该项工作衍生出的zkBridge目前也已经被应用于多个公司的实际产品（详情可见论文介绍页：zkbridge.org，工业界产品页：zkbridge.com）。

• 报告2摘要

  刘嘉源是姚班2019级本科生。本次Seminar他将介绍区块链的两大类扩容方案及其经济影响，并分享他与房智轩老师合作的关于基于支付信道网络（PCN）方案解决当前区块链系统的扩展性问题的研究，他们提出了使用拍卖竞标的实时递归路由（RTRR）算法，可以在PCN的动态场景中实现短路由时间、强隐私保护和高灵活性；此外，他们还研究了RTRR中的交易费用竞标过程并得出了均衡策略，证明了均衡策略中交易更倾向于通过成功率高的节点进行路由，从而获得更高的性能。

  欢迎全体同学参加~

本周日晚上 7:30 - 8:30，我们将在学堂 112 【线下】给大家带来计科 70 班吕欣学长的报告

• 吕欣：Privacy 101: Releasing the median of your data, privately

  吕欣目前是 UC Berkeley 理论组的二年级博士生，导师是 Avishay Tal 和 Jelani Nelson。他的研究兴趣是理论计算机科学，近期正在研究的问题包括为伪随机性，计算复杂性和差分隐私。本次报告中，他将介绍差分隐私中的一个问题：给定 n 个 [1,M] 中的整数，如何在满足私密性的情况下报告其中一个既不是前 1/3 小，也不是前 1/3 大的整数。

  【报告摘要】Say there is an array a[1…n] of integers from [1, M]. You are tasked to privately report an integer 1 <= y <= M such that y is sandwiched between n/3 smallest and largest elements of a[1…n]. Without privacy constraints, this problem is almost trivial. However, with privacy requirements (as per the Differential Privacy definition), it becomes much more challenging and interesting. In particular, it is impossible to release an approximate median when the inputs are arbitrary real numbers!

  So, let us fix a finite range [1, M]. Still, in this case, it takes more than a decade for people to figure out the smallest number n = n(M) of data (up to lower-order factors), so that the problem is possible to solve. I will describe the upper and lower bounds for this basic task, and survey its connections to several other basic tasks in privacy-preserving data analysis.

  欢迎全体同学参加~

本周我们将在学堂 112 给大家带来计科 91 班徐苇杭同学关于理论机器学习的报告

• 徐苇杭

  徐苇杭是姚班2019级本科生, 研究方向为理论机器学习. 本次seminar他将介绍他在华盛顿大学春研期间关于过参数化对训练神经网络收敛速率影响的工作. 使用梯度下降学习两层神经网络是深度学习理论的一个经典问题. 他们考虑在输入是标准高斯分布的情况下, 使用具有n个神经元的两层过参数化网络学习一个单独神经元的问题. 在n=1的情况下, 已有结果表明收敛速率是线性的. 而当n>1, 他们发现过参数化会导致收敛速率变为$\Theta(T^{-3})$ (其中T为迭代轮数), 这比精确参数化的情形指数级变慢.

  欢迎全体同学参加~

本周我们将在【线上】给大家带来计科92班高嘉煊同学关于强化学习与人机协同的报告

• 高嘉煊

  高嘉煊是姚班2019级本科生，研究方向包括多智能体强化学习，分布式强化学习系统与人机协同。本次seminar他将介绍他和合作者在基于强化学习的人机协同方向上的工作。零样本人机协同问题要求在不使用人类数据的情况下设计出能与人合作的智能体。此前的工作往往首先通过自博弈训练出大量策略构成策略池，然后针对策略池训练适应性策略。该框架的缺陷在于其假设测试合作者会与适应性策略遵循同一个任务奖励函数。然而，真实的人类自身的偏好往往与任务奖励相差很远。在这项工作中，高嘉煊和合作者提出新的训练框架Hidden-Utility Self-Play (HSP)，HSP直接将人类偏好建模成自博弈过程中的隐奖励函数，并训练有偏好策略得到增强的策略池。在Overcooked测试环境中的实验结果表明，HSP在与人类模型、人工脚本策略以及人类合作时能得到比基准方法更高的分数。同时，HSP策略也被人类玩家评为合作性最强的策略。该项工作Learning Zero-Shot Cooperation with Humans, Assuming Humans are Biased 发表于Eleventh International Conference on Learning Representations (ICLR 2023)

  欢迎全体同学参加~

本周我们将在【线上】给大家带来计科02班戴言同学关于强化学习理论的报告

• 戴言

  戴言是姚班2020级本科生，研究方向是强化学习理论。本次seminar他将介绍他和合作者对噪声强度会变化时的稀疏线性老虎机（sparse linear bandit）的研究。稀疏线性老虎机是强化学习理论中一个常见的基础模型。然而，在此前的研究中，研究者只考虑算法在最坏情况（即噪声总很强）的表现，得到了 sqrt(dT) 的表现下界，其中 T 是操作次数、d 是线性空间维度（省略稀疏度 s 这一远小于 d 的量）；人们还通过规约到线性老虎机，得到了匹配下界的算法。但事实上，在没有噪声的最好情况下，简单分治能达到 O(1) 的优秀表现。在这项工作中，戴言与合作者通过对传统规约方法的改进，得到了对噪声敏感的线性稀疏老虎机算法：它在最坏情况的表现为 sqrt(dT)，在最好情况的表现为 O(1)；在方差不均一时，其表现正比于 sqrt(d * 噪声方差之和)。这一算法实现了对噪声的自适应，完全还原了分治算法与 d、T 都无关的优秀表现，还保证了最坏情况的表现与下界相当。这项工作 Variance-Aware Sparse Linear Bandits 发表于 Eleventh International Conference on Learning Representations (ICLR 2023)。

  欢迎全体同学参加~

本周我们将给大家带来计科92班梅毅轩同学关于机器学习系统的报告

• 梅毅轩

  梅毅轩是姚班2019级本科生，研究方向是编译器、分布式系统与机器学习的交叉领域。本次seminar他将介绍他和合作者在强化学习快速训练系统上的工作。深度强化学习近年来在诸多领域取得了成功，但是样本效率和训练时间限制了深度强化学习更广泛的应用。在这项工作中，梅毅轩和合作者基于高样本效率的model-based强化学习方法EfficientZero，设计了一套高效的分布式训练系统SpeedyZero。通过异步模块化设计，基于共享内存的高效进程间通讯和CPU-GPU数据传输优化，SpeedyZero大幅减少了训练关键路径的延时，提升了训练速度。同时，他们在算法上也提出了两项改进：为了解决在样本数和训练步数有限时value network训练不稳定的问题，他们提出了Priority Refresh；为了解决大规模并行训练和大batchsize下训练不稳定的问题，他们提出了Clipped LARS。在系统和算法的共同优化下， SpeedyZero仅需35分钟就可以在Atari100k测试集上取得人类水平，相较EfficientZero取得了14.5倍的速度提升。这项工作SpeedyZero: Mastering Atari with Limited Data and Time发表于Eleventh International Conference on Learning Representations (ICLR 2023)

  欢迎全体同学参加~

本周我们将给大家带来计科92班赵时予同学关于人工智能的报告

• 赵时予

  赵时予是姚班2019级本科生，研究方向是数据挖掘和自然语言处理。本次seminar他将介绍他和合作者在知识图谱推理上的研究成果。知识图谱嵌入是目前对不完整的知识图谱进行推理的主流方法。然而，受限于固有的浅层和静态架构，它们很难处理复杂逻辑的查询。在这项工作中，赵时予和合作者提出了适用于知识图谱的transformer架构(kgTransformer)及相应预训练和微调策略。 他们设计了一个三元组转换方式调整输入格式，引入混合专家系统 (MoE)扩展模型，将复杂的逻辑推理转换为为掩码预测任务，并提出了两阶段掩码预训练策略以提高可移植性和通用性。此外，kgTransformer有很强的可解释性，可以通过提供完整的推理路径来解释给定的答案。该论文Mask and Reason: Pre-Training Knowledge Graph Transformers for Complex Logical Queries发表于Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (2022).

  欢迎全体同学参加~

本周我们将为大家带来两个报告，本页是第二场，内容为刘鹏宇同学对量子纠缠探测的研究报告。

• 刘鹏宇

  刘鹏宇是姚班2019级本科生，研究方向是量子信息与量子计算机系统。本次seminar他将介绍他和合作者们在量子纠缠探测上的研究成果。量子纠缠是量子计算中重要的资源。然而反直觉的是，即使纠缠态几乎占据整个量子态空间，成功探测到纠缠的难度却非常高。在本工作中，刘鹏宇和合作者们通过一种系统的方法来评估纠缠判据的探测能力，发现了纠缠判据的效率和有效性之间的限制。对于一个与环境耦合的随机系统，他们证明了，任何基于单拷贝测量的纠缠判据，都需要指数多的测量来有效地探测纠缠。否则，该判据的探测能力将双指数衰减。此外，如果允许多拷贝联合测量，纠缠判据的有效性可以得到指数级的提高，这意味着在纠缠探测问题上的量子优势。

  该成果论文Fundamental Limitation on the Detectability of Entanglement在PRL [Phys. Rev. Lett. 129, 230503 (2022)]发表，并被选为Editors’ Suggestions。

  欢迎全体姚班同学参加！

本周我们将为大家带来两个报告，本页是第一场，内容为陈一镭老师对近年来密码学研究新进展的概述。

• 陈一镭

  陈一镭老师是交叉信息研究院助理教授，主要研究方向是密码学，及其与量子计算、复杂度理论和机器学习的交叉方向。在本次报告中，陈老师将分享密码学研究近年来的重要进展，包括格问题在密码学中的应用，密码学与复杂度理论和量子计算方向上的新动向。

  欢迎全体姚班同学参加！

  （此外，陈一镭老师本学期正在开设“密码学基础”课程，欢迎对密码学感兴趣的同学选修或旁听~）

本周我们将在【线上】为大家带来任翰林学长关于计算复杂性理论的报告！

• 任瀚林

  任瀚林是姚班2016级毕业生，现为牛津大学博士二年级，导师是Rahul Santhanam，研究方向是计算复杂度理论。本次seminar他将介绍他和合作者们在电路值域回避问题（circuit range avoidance）上的研究成果。 概率方法（probabilistic method）是组合数学中非常重要的技术，很多组合对象的存在性都可以用概率方法证明。最典型的例子是电路复杂度下界（circuit lower bounds）：用概率方法很容易证明非常强的电路复杂度下界。但是，概率方法是非构造性的，也就是说就算我们用概率方法证明了某个组合对象的存在性，我们也并不知道应该如何显式地（explicitly）构造出符合条件的组合对象。最近的研究表明，概率方法可以由电路值域回避问题（range avoidance problem）刻画，如果该问题有高效的确定性算法，那么所有由概率方法推出的存在性证明都可以改造成构造性证明。本次seminar将介绍在解决值域回避问题上的最新进展，以及这些进展带来的电路复杂度中新的推论。

  欢迎全体姚班同学参加！

本周我们将在【线上】为大家带来计科92班李嘉图同学关于计算复杂性理论的报告！

• 李嘉图

  李嘉图同学是2019级（计科92）本科生。本次Seminar，他将分享春研期间在英国华威大学Igor C. Oliveira助理教授指导下进行的关于计算复杂性下界不可证明性的研究。证明无条件计算复杂度下界，如NP≠P或电路复杂度下界是计算复杂度理论中重要的开放问题。但经过数十年的探索，我们目前仍缺少能够解决这些基本问题的工具。这启发我们研究证明计算复杂性下界的元数学难度，即说明计算复杂性下界在某些数学理论中的不可证明性。在本次报告中，李嘉图同学将向大家介绍如何在有界算术（Bounded Arithmetic）这一皮亚诺算术（Peano Arithmetic）的重要片段中证明计算复杂性下界的不可证明性，以及有界算术中可证性的一个博弈论意义上的刻画。 欢迎全体姚班同学参加！

本周我们将在【C楼活动室C220】为大家带来计科91班王子轩同学关于机器学习理论的报告！

• 王子轩

  王子轩同学是2019级（计科91）本科生。2022年春研期间，他在鬲融副教授指导下进行了机器学习理论与非凸优化方向的研究。本次Seminar，他将分享他在春研期间进行的Edge-of-Stability理论解释的工作。Edge of Stability (EoS) [Cohen et al. ICLR 2021] 是发生在神经网络使用梯度下降（gradient descent）进行训练的过程中发生的一种普遍现象：对于一个固定的学习率（step size），神经网络的Hessian矩阵的最大特征值从训练开始会逐渐增大, 随后保持在2/(step size)上下震荡。这虽然违反了传统学习理论中保证梯度下降能减小损失函数的L-smoothness条件，但事实上，损失函数仍然能够呈现非单调下降的趋势。什么样的函数能发生EoS现象？在EoS发生时，如何分析模型的收敛性与训练轨迹？在本次报告中，他将介绍其工作中提出的【能发生EoS现象的一个最简模型】与【其在训练过程中的收敛轨迹】，以及这个简单模型与【现实模型的联系】。

  欢迎全体姚班同学参加！

本周我们将在【学堂112】为大家带来计科91班胡子晗同学对量子密码学的介绍！

• 胡子晗

  量子密码学

  胡子晗是姚班2019级（计科91）的本科生。2022年春研期间，她在Prabhanjan Ananth (UCSB) 和 Henry Yuen (Columbia University) 的指导下进行了量子密码学方向的研究。量子货币 (Quantum Money) 利用量子不可克隆性原理构造安全的货币系统，是最著名的不可克隆原语 (Unclonable Primitive) 之一。已知的构造量子货币的方法要么基于未经广泛验证的假设，要么基于较强的密码学原语。这要求我们对构造量子货币的难度有更深入的理解。本次seminar上，她将介绍一类量子货币和抗碰撞的哈希函数 (Collision-Resistant Hash Functions) 之间的黑盒不可规约性 (Black-Box Separation)，这是不可克隆原语和其他密码学原语的第一个不可规约性结果。

本周我们将在【线上】为大家带来姚班学长贾志豪老师对【人工智能系统】的介绍！

• 贾志豪

  本次Seminar我们非常荣幸请到了卡内基梅隆大学计算机系助理教授贾志豪老师为我们介绍计算机系统领域的前沿研究。贾志豪老师2013年毕业于清华姚班，之后在斯坦福大学取得了博士学位。他的研究兴趣主要集中在为机器学习、量子计算和大规模数据分析等新兴应用领域构建系统。本次talk的主要内容是机器学习优化的自动生成，将会介绍计算图优化器TASO和分布式训练优化器FlexFlow。

  Automated Discovery of Machine Learning Optimizations

  Abstract: As an increasingly important workload, machine learning (ML) applications require different performance optimization techniques from traditional runtimes and compilers. In particular, to accelerate ML applications, it is generally necessary to perform ML computations on heterogeneous hardware and parallelize computations using multiple data dimensions, neither of which is even expressible in traditional compilers and runtimes. In this talk, I will describe my work on automated discovery of performance optimizations to accelerate ML computations. TASO, the Tensor Algebra SuperOptimizer, optimizes the computation graphs of deep neural networks (DNNs) by automatically generating potential graph optimizations and formally verifying their correctness. TASO outperforms rule-based graph optimizers in existing ML systems (e.g., TensorFlow, TensorRT, and TVM) by up to 3x by automatically discovering novel graph optimizations, while also requiring significantly less human effort. FlexFlow is a system for accelerating distributed DNN training. FlexFlow identifies parallelization dimensions not considered in existing ML systems (e.g., TensorFlow and PyTorch) and automatically discovers fast parallelization strategies for a specific parallel machine. FlexFlow has been used to train production ML models that do not scale well in current ML systems, achieving over 10x performance improvement.

  本次报告不需要人工智能和计算机系统的前置知识，欢迎全体同学参加！

本周我们将在【学堂 112】为大家带来原计划在上周的葛程同学关于【人工智能】的报告！

• 葛程

  葛程同学是2019级（计科92）本科生。本次Seminar他将介绍他在2022年春研期间在Sven Koenig教授（USC）指导下进行的多智能体寻路方面的研究。多智能体寻路（MAPF）问题是为多个智能体规划路径的基本问题，其中的关键约束条件是多个智能体能够同时遵循这些路径而不相互碰撞。多智能体寻路的应用包括自动仓库管理与自动车辆驾驶。多目标多智能体寻路（MO-MAPF）问题将原来的问题扩展到为多智能体寻找无碰撞路径的所有帕累托最优解。目前最先进的 MO-MAPF 算法，即多目标冲突搜索（MO-CBS）算法使用的标准分支策略会导致重复的搜索树节点。在本次报告中，我们将介绍 MO-CBS 提出了两种新的分支策略，即 cost-splitting 和 disjoint cost-splitting。实验结果表明，disjoint cost-splitting 将 MO-CBS 的速度提高了两个数量级，并在各种情况下大幅提高了其成功率。

  本次报告不需要人工智能的前置知识，欢迎各位同学参加！

本周我们将为大家带来【两个】报告，以下是第二个：

• 赵梓硕

  赵梓硕是姚班2015级毕业生，现为UIUC ISE博士二年级，导师是Yuan Zhou，科研兴趣是机制设计。这次seminar将介绍他与导师Yuan Zhou和纽约大学商学院Xi Chen教授的工作。

  区块链交易费机制是保障区块链系统高效、稳定运行的重要保障，如何设计一个能够使用户诚实出价且防止矿工与用户合谋的交易费机制，是当前区块链机制设计面临的重要挑战之一。本次seminar他将介绍其工作中研究的同时满足贝叶斯-纳什激励相容（BNIC）且可以防止矿工与至多1名用户合谋（1-SCP）的机制，并证明了其设计的机制可在用户数充分多时实现最优矿工利润的常数比例近似。该工作还从理论角度上讨论了EIP-1559等交易费机制中销毁部分虚拟货币的必要性，并证明了在一定的合理假设下，同时满足BNIC与1-SCP且具有静态区块大小的非平凡交易费机制必然销毁部分虚拟货币，从而证明了诚实且防共谋的区块链交易费机制无法同时在空间与货币上达到充分高效的理论限制。

  此论文已被CESC 2022会议接收

  文章链接

本周我们将为大家带来【两个】报告，以下是第一个：

• 龚维元

  龚维元是姚班2019级（计科92）的本科生。本次seminar介绍他2022年春研期间在Scott Aaronson教授（UT Austin）指导下进行的shadow tomography方面的理论研究。量子信息中一个重要的问题是如何从实验的测量中获得量子系统的信息。一个传统的办法是量子态层析(quantum state tomography)，这种办法可以通过测量复原完整的量子态密度矩阵，但是需要指数量级的样本复杂度（sample complexity）。在很多情况下，我们只需要获得对于量子态的量子测量的结果，因此shadow tomography的技术被发展出来。在量子测量是只有两种结果的情况下，shadow tomography可以提供很小的样本复杂度。而当测量结果数量增加时，目前的shadow tomography的样本复杂度关于测量结果数量会四次方增长。为解决这一问题，我们提出了一种基于在线学习（online learning）的shadow tomography算法，可以容许线性增长的样本复杂度。我们还证明这一算法关于测量结果数量的依赖是最优的。

  文章链接

本周六晚上 19:30，计科91班的冯时同学会在学堂 112 分享他在春研时完成的工作，时长为 45 分钟报告 + 15 分钟提问。

• 冯时

  冯时是姚班2019级（计科91）的本科生。2022年春研期间，在Yiling Chen教授（哈佛大学）的指导下，他与Fang-Yi Yu教授（乔治梅森大学）合作进行了同伴预测方面的理论研究，论文发表于计算机顶会NeurIPS 2022上。同伴预测（peer prediction）是一个信息收集的机制设计问题，目标是通过奖励机制让诚实的信息报告成为每个人的最优选择。过去的理论工作中都需要假设每个人都使用一个固定的混合策略（consistent strategy assumption），和一些实际场景并不相符。本次seminar上，他将介绍相关协议机制（correlated agreement mechanism）如何保证具有学习能力的个体策略收敛到诚实的信息报告，并给出策略能否收敛和学习算法是否无悔之间的逻辑关系。

本周六（5月28日）下午13:00，线上，刘研绎学长、刘易同学会分享自己的工作，时长约为一到两小时。

• 刘研绎：Leakage-Resilient Hardness v.s. Randomness

  刘研绎是姚班2015级（计科50）毕业生，现为 Cornell 大学博士三年级，导师是 Rafael Pass 和 Elaine Shi，研究方向是密码学。这次 seminar 将介绍他和 Rafael Pass的工作。随机算法是否能被确定性算法高效的模拟是复杂度理论的一个中心问题。本次 seminar 他将介绍抗泄露难度刻画了 prBPP 的去随机化。

• 刘易：稳定的市场细分对抗价格歧视

  刘易是姚班2018级的本科生，本次seminar他会带来在计算经济学方面的研究工作。我们分析了稳定和群体稳定的市场细分，消费者可以在定价之前在不同的市场之间流通。自由流通是数据保护法规的法定要求。我们证明了稳定和群体稳定的市场细分可以实现满足下列条件的消费者剩余和生产者剩余的每一种组合：（i）生产者剩余保持在统一垄断定价水平，（ii）消费者剩余取最大消费者剩余和统一垄断下消费者剩余之间的任何值。与统一垄断相比，在任何稳定或群体稳定的细分下，没有消费者的境况更差。此外，买家的最优结果可以在策略性消费者的支持下存在。因此，我们的结果证明了流通消费者存在时三级价格歧视的帕累托最优，揭示了数据保护法规的福利含义。

本周六（4月30日）下午13:00，学堂112，赵心怡同学、胡扬同学会分享自己的工作，时长约为一到两小时。

• 赵心怡：Introduction to some interesting start-ups or unicorn companies at home and abroad

  赵心怡是姚班2018级本科生。本次seminar她将会分享自己在投资机构实习的一些所见所闻，以及介绍一些有趣的国内外计算机领域的初创公司、独角兽和最近上市的公司，简单梳理目前计算机方向的投资热点。希望可以和同学们探讨计算机领域未来的创新创业机会。

• 胡扬：线性时变系统中模型预测控制的性能分析——基于微扰法的分析框架

  胡扬是姚班2018级（计科81）本科生。2021年春研期间，在Adam Wierman教授（加州理工大学）的指导下，他与姚班校友林一衡等人合作进行了在线最优控制方面的理论研究，论文发表于计算机顶会NeurIPS 2021上。模型预测控制（model predictive control, MPC）是一种流行且实用的在线最优控制算法，其性能在线性时不变（LTI）系统中已经给出了一些理论保证，但在带一般代价函数的线性时变系统中相关性能保证还比较缺乏。本次seminar上，他将介绍一种新的基于扰动－响应分析的框架，并利用该框架证明线性时变系统中MPC控制器的动态遗憾界（dynamic regret）、竞争比（competitive ratio）等理论性能保证。

本周日（4月3日）晚上19:00，学堂112，王修涵同学、郑舒冉学姐会分享自己的工作，时长约为一到两小时。

• 王修涵：Constant Approximating Parameterized k-SetCover is W[2]-hard

  王修涵是姚班2019级本科生。本次seminar他将会介绍他和任轩笛、孙奕灿，以及他们的导师林冰凯在参数不可近似性方面的工作。k-SetCover是一个很基础的问题：给定集合U的n个子集，询问是否能否选出k个子集使得它们的并为U？在多项式时间内，假设P≠NP，近似比为ln(n)的贪心算法是最优的；在参数时间(f(k)poly(n))内，这个问题是经典的W[2]-hard问题。一个自然的问题是，k-SetCover的任意常数近似版本是否也是W[2]-hard的呢？本次talk将会介绍如何使用极值图(Threshold Graph)来解决这个问题。同时，在非参数的意义下，这种方法也可以避开PCP定理来证明多项式时间内o(log(n)/loglog(n))的近似比上界，即使已知答案不超过O(log^2(n)loglog(n))。

• 郑舒冉：The Limits of Multi-task Peer Prediction

  郑舒冉是姚班2013级本科生，现在是哈佛大学的博士生。本次seminar 她将介绍她在计算经济学方向关于peer prediction 的工作。信息和数据是AI最根本的驱动力，而信息和数据很多时候是靠人工获得的，比如机器学习的数据标记(data labeling)，交易平台的商品打分(product review)，学术会议的同行评议(peer review) 等等。在这些问题中，人们提供的信息往往难以验证真实性或是准确性。Peer prediction 研究的问题就是当设计者无法直接验证信息的质量时，如何从人们手中获取真实的信息。本次seminar她将介绍与 Yiling Chen 和 Fang-Yi Yu 合作的关于peer prediction基础理论的工作。

本周日（3月27日）下午15:00，学堂112，吴瑾昭、闫书弈学长会分享自己的工作，时长约为一到两小时。

本次seminar是和北大信科peer talk合办的。

• 吴瑾昭：Learning Bilateral Trade from Finite Samples

  吴瑾昭是北大图灵班2018级本科生，本次seminar他将会介绍他在机制设计方面的工作。

  We study the problem of approximating social welfare in bilateral trade using a finite number of samples. The seminal result of Myerson(1983) shows that no Bayesian incentive compatible, individually rational, and budget balance mechanism can achieve the optimal social welfare even in bilateral trade, arguably the simplest two-sided market, where a seller is selling an item to a buyer. Recent results show that one can already obtain a constant factor approximation to the optimal welfare using a single sample from the seller’s distribution. In this paper, our goal is to understand what approximation ratios are possible if the designer has more than one but still finitely many samples. This is usually a technically more challenging regime. We propose a new family of mechanisms that we refer to as the “order statistic mechanisms” and provide a complete characterization of their approximation ratios for any fixed number of samples. Using the characterization, we numerically compute the approximation ratios obtained by the optimal order statistic mechanism for small sample sizes (no more than 10 samples), and observe that they significantly outperform the single sample mechanism.

• 闫书弈：The Power of Multiple Choices in Online Stochastic Matching

  闫书弈是姚班2018级（计科80）本科生。本次seminar他将会介绍他在在线匹配问题上的研究。

  Online stochastic matching is a model in which we know an i.i.d. distribution for online vertices and need to match each online vertex immediately and irrevocably. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. We introduce two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting. For edge-weighted matching with free disposal, We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality.

本周六（3月19日）下午13:00，学堂112，吕欣、盛翊伦学长会分享自己的工作，时长约为一到两小时。

• 吕欣：On the Robustness of CountSketch to Adaptive Inputs

  吕欣是姚班2017级（计科70）本科生，现在是加州大学伯克利的博士生，导师是Avishay Tal和Jelani Nelson。本次seminar他将会介绍他在Sketching Algorithm方面的工作。CountSketch是一种常见的Sketching算法，这种算法可以以较小的内存处理一个数据流，并支持对数据流中的 heavy-hitter 的查询。我们证明了经典的CountSketch实现不是鲁棒的：它可以在线性于Sketch大小的查询内被针对性地攻击。我们同时提出了一个鲁棒的实现，可以容许平方级别的查询次数。

• 盛翊伦：Why the Valency Argument Fails

  盛翊伦是姚班2018级（计科80）本科生。本次seminar他将会介绍他于2020年暑假在多伦多大学的Faith Ellen教授的指导下进行的分布式计算理论方面的研究。二值共识问题（Consensus）的不可能性结果是许多分布式计算模型的基础，而“价论据”（Valency Argument）是证明这一类不可能性结果的工具。本次seminar他将介绍“价论据”在一些分布式计算模型下的一种推广形式，并证明其无法证明多值共识问题（k-Set Agreement）的不可能性结果，以此显示“价论据”的局限性。

本周六（12月11日）上午10:00，学堂112，王康宁、刘壮学长会分享自己的工作，时长约为一到两小时。

• 王康宁：近似有效的双边交易（Approximately Efficient Bilateral Trade）

  王康宁是姚班2013级（计科30）本科生，现在是杜克大学的博士生。本次 seminar他将会介绍他在计算经济学方面的工作。我们考虑一个买家和一个卖家之间交易一个物品。著名的Myerson-Satterthwaite不可能性定理指出: 没有“合理的”交易机制能对社会整体最优; 即没有“合理的”机制能保证买家估价超过卖家成本时完成交易。由此，我们自然要问, 是否存在“合理的”交易机制能让交易对社会整体的贡献达到理想情况的常数比例。我们在这一工作中证实了这一猜想。工作的合作者有Google研究院的邓原, 毛杰明, 和Balasubramanian Sivan。

  ArXiv链接

• 刘壮：深度学习的高效性和准确性（Accurate and Efficient Deep Learning for Visual Recognition）

  刘壮是姚班2013级（计科30）本科生，现在是加州大学伯克利分校的博士生。本次Seminar他将介绍他近年来一系列在深度学习高效性和准确性方面的研究工作。他将介绍或者讨论

  1）一系列网络剪枝方法上的实验，发现的现象以及由此引起的反思

  2） 一个利用神经网络和计算机视觉任务的特性做到高效的”任意时刻” (Anytime)预测的框架

  3）Transformers是否在计算机视觉领域已经超越卷积神经网络

本周六（12月4日）下午一点到三点，学堂112，陶润洲、罗辑同学会分享自己的工作，时长约为一到两小时。

• 陶润洲：Data-Driven Automated Invariant Learning for Distributed Protocols

  陶润洲是姚班2015级毕业生，现为哥伦比亚大学博士生。本次seminar他将介绍他最近在OSDI上的关于系统验证的工作。由于非确定性，分布式系统很难正确实现。找到分布式协议的归纳不变量是验证分布式系统的正确性的关键步骤，但即使对于简单的协议也需要很长时间才能做到。我们提出了一个数据驱动的学习分布式系统归纳不变量的新方法。它通过模拟分布式协议生成不同实例大小的数据并将状态记录为样本，并从小的公式开始枚举所有可能的最强不变量。然后它使用SMT求解器尝试安全性，并尝试修改当前不变量，重复该过程直到最终成功。实验证明此方法可以自动验证13个常见的分布式协议，相比其他方法可加速超过两个数量级。

• 罗辑：Compact Adaptively Secure Attribute-Based Encryption

  罗辑是姚班2014级本科生，本次Seminar他将介绍他和他的研究生导师林蕙佳在密码学中的工作。基于属性的加密(attribute-based encryption)是支持细粒度访问权限控制的公钥加密算法，可以看作访问控制列表(access control list)的密码学实现。他们最近的工作依托一个易于理解的新框架和随机化编码的一种新安全性定义，构造了高效且适应性安全的属性加密，新方案支持算术分支程序(arithmetic branching program)、NFA、NL图灵机表达的访问策略。本次报告中，他将介绍支持算术公式(arithmetic formula)的属性加密之构造，并讲述这段研究中最有趣的经历。

本周日（11月28日）下午三点到五点，学堂112，范致远、武弘勋同学会分享自己的工作，时长约为一到两小时。

• 范致远：The Exact Complexity of Pseudorandom Functions

  范致远、李嘉图和杨天祺是姚班2019级本科生。本次seminar范致远将介绍他们在密码学与计算复杂性理论中的工作。伪随机函数(pseudorandom functions)是无法与随机函数区分开的函数族。作为密码学许多构造的起点是密码学的基础，构造高效的伪随机函数在理论及应用中有多种意义。他们最近的工作研究了伪随机函数的电路复杂性，在多个重要的电路复杂性类中对伪随机函数给出了几乎紧的上界与下界。这些上下界结果为电路复杂性理论提供了新的见解，也刻画了一些障碍。本次talk中，他们将主要介绍在一般电路(general circuits)下的结果，包括如何在 2n+o(n) 的电路复杂度内构造伪随机函数（假设伪随机函数存在），以及一个与之相对应的 2n-O(1) 的下界证明。

  文章链接

• 武弘勋：Element Distinctness, Birthday Paradox, and 1-out Pseudorandom Graphs

  武弘勋是计科80本科生。本次seminar将会介绍在春研期间，他和陈立杰（计科30）、金策（计科60）两位姚班学长，以及他们的导师Ryan Williams合作的工作。Element Distinctness 问题是一个很基础的计算问题：给出只读的 n 个数，如何判断它们是不是两两不同？在比较模型（Comparison Model）下，姚先生 [Yao88] 证明了时间复杂度 S 和空间复杂度 T 的最优tradeoff为 ST = O(n^(2 ± o(1)))。而在RAM模型（读入支持随机只读访问）下，假设 Random Oracle 存在，[BCM13] 证明了存在一个算法可以超越这个比较模型的最优tradeoff，它的时间空间 tradeoff 为 ST^2 = Õ(n^3)。其中最有趣的Open Problem是，在 RAM 模型下，当空间限制为 Õ(1) 的时候，不假设 Random Oracle，是否能做到 Õ(n^(3/2)) 的时间复杂度？本次talk中，将会介绍如何利用伪随机性来取代 Random Oracle, 从而解决这个 Open Problem。同时对于 Subset Sum 问题，[BGNV18] 假设 Random Oracle 存在，提出了一个多项式空间，O*(2^(0.86n)) 时间的算法。这个构造同样也可以取代其中的 Random Oracle 假设。

  文章链接

本周六（11月20日）中午12:30，学堂112，姚顺雨、罗雨屏学长会分享自己的工作，时长约为一到两小时。

• 姚顺雨：基于语料迁移的涌现——自然语言连接（Linking Emergent and Natural Languages via Corpus Transfer）

  姚顺雨是姚班2015级（计科50）本科生，现在是普林斯顿大学的博士生，导师为Prof. Karthik Narasimhan。本次 seminar他将会介绍他在自然语言处理方面的工作。今天的自然语言处理（NLP）主要基于大量静态文本数据（如Wikipedia）上的训练，但是人类并非从这样复杂、被动的语料中习得（acquire）语言，而是基于对环境的感知（perceptual grounding）和他人（父母）的交互（communication）逐渐产生愈发复杂的语言能力。姚顺雨学长将介绍emergent communication，一类试图使机器涌现语言能力的研究，其进展和局限，以及他们最新的工作如何试图基于自然语言更好地利用、分析、衡量机器涌现语言。

• 罗雨屏：Learning Barrier Certificates: Towards Safe Reinforcement Learning with Zero Training-time Violations

  罗雨屏是姚班2013级（计科30）本科生，现在是普林斯顿大学的博士生，导师为 Prof. Sanjeev Arora。本次 seminar 他将会介绍他在安全强化学习方面的工作。安全性一直是强化学习算法具体应用的一个痛点。给定一个不安全状态的集合，如何才能做到不去访问那些现在暂时安全，但是未来一定不安全的状态呢？这次罗雨屏学长将介绍他和合作者提出的新算法，可以在不用先验知识的情况下在一些状态空间连续的任务上做到训练时不访问任何不安全的状态。

本周日（11月14日）晚20:00，学堂112，任翰林、高睿泉和何中天同学会分享自己的工作，时长约为一到两小时。

• 任翰林：Faster algorithms for distance sensitivity oracles

  任翰林是姚班2016级（计科60）本科生，现在是牛津大学的博士生，导师为Prof. Rahul Santhanam。本次seminar将会介绍他在distance sensitivity oracles (DSOs)方面的工作。给定一张n个点、边权在[1, M]中的有向图G = (V, E)，我们要构造一个数据结构求解如下询问：给定一个起点u和终点v，以及一个坏掉的点或者边f，求出从u到v不经过f的最段路径长度。本次talk会展示如何用快速矩阵乘法实现一个预处理时间为O(n^{2.5794}M)、查询时间为O(1)的DSO。

• 高睿泉&何中天：Improved Online Correlated Selection

  高睿泉和何中天是姚班2018级（计科80）本科生。本次seminar会介绍他们在在线二分图匹配方面的研究。在线二分图匹配问题是在线算法的核心问题之一。尽管带有点权的问题的早在1990年就被解决，带有边权的问题直到去年才有突破平凡下界的方法。这一方法用到Online Correlated Selection(OCS)，并已经被应用于其他的在线匹配问题上。本次talk是在上述工作的基础上提出了OCS的改进算法以及OCS的推广，并改进了相关的在线匹配问题的近似比。

本周六（10月23日）下午13:00，学堂112，黎天鸿、徐海珂同学会分享自己的工作，时长约为一到两小时。

• 黎天鸿：From Wearables to Invisibles: Human Sensing with Radio Signals

  黎天鸿是姚班2014级（计科40）本科生，现为MIT四年级博士生，导师为Dina Katabi教授，目前的主要研究兴趣为机器学习在无线感知中的应用。传统的人体无线感知大多依靠启发式算法，以定位和测速为主，缺乏精细成像的能力。本次 seminar他将介绍基于无线雷达信号，应用机器学习进行精细成像和处理复杂任务的的困难以及解决方法。除此之外，他还会分享他对科研方向选择和海外博士申请上的一些想法。

• 徐海珂：Fine-Grained Gap-Dependent Bounds for Tabular MDP

  徐海珂是姚班2018级（计科80）本科生。本次seminar他将介绍他在理论强化学习方面的研究。强化学习算法在实际训练中面临着很高的样本数量，近些年来gap-dependent bound的提出有助于利用特定问题的性质，对算法给出更强的理论保证，从而可能节省大量的数据。然而，Simchowitz and Jamieson (2019)提出，目前所有的强化学习算法都存在着“过度探索”问题，徐海珂同学将介绍他与合作者提出的新算法，他们的算法成功解决了“过度探索”问题，并且算法的regret在某种程度上达到了理论下界。

本周日（10月17日）晚上19:30，学堂112，张辰逸、岑若虚同学会分享自己的工作，时长约为一到两小时。

• 张辰逸：Classical and quantum algorithms for escaping from saddle points

  张辰逸是姚班2018级（计科80）本科生，本次 seminar 他将介绍他在量子优化算法方面的工作。给定一个 R^n 上的光滑函数，允许你在不同位置处查询函数值和梯度。你最少用多少次询问，可以找到一个局部最小值点？在经典计算机上，之前最好的算法需要 Õ(log^6(n)/ε^1.75) 次查询才能找到一个ε-近似的二阶局部最小值点。张辰逸同学将介绍自己的新工作 —— 在经典计算机上，他们提出的新算法仅需 Õ(log(n)/ε^1.75) 次查询；而在量子计算机上，Õ(log^2(n)/ε^1.75) 次查询即可，甚至不需要查询梯度信息。

• 岑若虚：Minimum Cuts in Directed Graphs via Partial Sparsification

  岑若虚是姚班2015级（计科50）毕业生，现为杜克大学一年级博士生。本次seminar他将介绍他在图论算法方面的研究。最小割问题是图论中的经典问题，研究的是如何将一个图分成两部分，使得跨越不同部分的边权之和最小。对于 n 个点 m 条边的带权有向图，岑若虚及其合作者提出了一个新的算法，只需要 Õ(n*max(m^{2/3},n)) 的运行时间。在此之前人们已知的最好结果是 Hao & Orlin (1993) 提出的 Õ(nm) 的最小割算法，已保持记录 30 年之久。

本周日（10月10日）晚上19:30，六教6B201，李博洋、赵梓硕同学会分享自己的工作，时长约为一到两小时。

• 李博洋：More Communication Lower Bounds for Information-Theoretic MPC

  李博洋是姚班2016级（计科60）毕业生，现工作于量化交易公司Jane Street，本次seminar他将介绍他本科期间在多方安全计算通讯复杂度下界方面的工作。他还会在Q&A环节分享他在Jane Street的工作体验。

  Secure Multi-Party Computation (MPC) is a modern and important field in the studies of cryptography. In this talk, instead of introducing a better protocol, he proposes and proves a general lower bound for communication complexities as a function of properties of the function “f” for a general and important class of functions where n parties with a passively corrupted minority compute a function y_i=b_i*f_i([x_1,x_2,…,x_n]) where f_i is any function.

• 赵梓硕：Dynamic Car Dispatching and Pricing: Revenue and Fariness for Ridesharing

  赵梓硕是姚班2015级（计科50）毕业生，现为UIUC博士生。本次seminar他将介绍他在共享单车平台设计方面的研究。

  A major challenge for ridesharing platforms is to guarantee profit and fairness simultaneously, especially in the presence of misaligned incentives of drivers and riders. We focus on the dispatching-pricing problem to maximize the total revenue while keeping both drivers and riders satisfied. We study the computational complexity of the problem, provide a novel two-phased pricing solution with revenue and fairness guarantees, and develop a dynamic (a.k.a., learning-while-doing) algorithm that actively collects data to learn the demand distribution during the scheduling process. We also conduct extensive experiments to demonstrate the effectiveness of our algorithms.

本周六（9月25日）下午1:00，学堂112，将举行本学期第一次seminar。本次有两位七字班的学长来分享，时长约为一到两小时。

来自MIT七字班的毛啸同学，将会分享自己关于Tree Edit distance、刚刚被FOCS 2021接收的single author paper。

来自计算机系七字班的刘潇同学，将会分享自然语言处理中预训练模型的前生今世与未来。

• 毛啸：Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance

  The (unweighted) tree edit distance problem for n node trees asks to compute a measure of dissimilarity between two rooted trees with node labels. The current best algorithm from more than a decade ago runs in O(n^3) time. This algorithm would also work for the weighted tree edit distance problem, which cannot be solved in truly sub-cubic time under the APSP conjecture. In this talk, we break the cubic barrier by showing an O(n^{2.9546}) time algorithm for the unweighted tree edit distance problem by reducing it to max-plus product of bounded-difference matrices, which can be solved in truly sub-cubic time.

  arxiv链接

• 刘潇：Pretrained Language Models: Past, Present and Future

  Natural Language Processing (NLP) is one of the most important application fields of machine learning. As the emergency of giant pretrained language model GPT-3, NLP has come to its turning point as AlexNet for computer vision. In this talk, we will briefly review the history of pretrained language models, and focus on the current breakthroughs and challenges brought by BERT and GPT-3. Finally, we will discuss several fundmental problems of NLP and how researchers now think of them.

本周日（6月6日）下午1:00，学堂112，王若松、卢睿同学会分享自己的工作，时长约为一到两小时。

• 王若松：Recent Progress on the Theoretical Understanding of Reinforcement Learning

  王若松是姚班2013级（计科30）毕业生，现为CMU四年级博士生，导师为CMU机器学习系的Ruslan Salakhutdinov教授。目前研究方向为机器学习理论，特别是强化学习理论。本次seminar他将介绍近期强化学习理论领域的最新进展，还会分享他对机器学习方向博士申请和职业发展上的一些理解。

• 卢睿：On the Power of Multitask Representation Learning in Linear MDP

  卢睿是姚班2016级（计科60）本科生，目前的主要研究兴趣为强化学习和神经网络架构设计分析。强化学习往往需要大量的样本，使用多任务的表征学习来减少训练所需的样本是实践中已经非常常用的方法，但理论研究还比较欠缺。本次seminar卢睿同学将介绍自己近期的工作。通过分析linear MDP的理论模型，他们证明了使用多任务学习得到的表征可以极大地减少样本复杂度，并在一个小例子中验证了该结果。

本周日（5月30日）下午1:00，学堂112，彭天翼、李辰星同学会分享自己的工作，时长约为一到两小时。

• 彭天翼：Causal Inference on Panel Data with General Treatment Patterns

  彭天翼是姚班2013级（计科30）毕业生，现为MIT四年级博士生，导师为MIT Operation Research Center的Vivek Farias。目前研究方向为因果推断和机器学习，处于计算机科学、经济学、和运筹学的交叉领域。本次seminar他将介绍如何改进机器学习中的低秩矩阵理论，为经济学中的政策分析和因果推断提出新的方法和分析。他还会分享他对运筹学方向博士申请和职业发展的一些理解。

• 李辰星：GHAST: Breaking Confirmation Delay Barrier in Nakamoto Consensus via Adaptive Weighted Blocks

  李辰星是姚班2013级（计科30）毕业生，现为交叉信息院四年级博士生，导师为姚期智。目前研究方向为区块链系统。本次seminar他将介绍一个有关区块链共识协议的工作。近年来，很多工作提出了新的共识协议来提升区块链协议的吞吐率。然而，这些工作没有突破中本聪共识对区块确认时间的制约。GHAST 提出了一种新的思路，它基于 GHOST 协议设计，突破了中本聪共识中确认时间的限制，并通过自适应地调节区块权重解决了 GHOST 协议中 liveness 攻击问题。他还会介绍一些 Conflux 在开发过程中遇到过的问题，探讨区块链的学术研究与工程开发之间的差异。

• 【匿名提问】
• 【重复一遍时间地点】本周日（5月30日）下午1:00，学堂112点击此处进行时区转换

本周日（5月23日）下午1:00，六教6A102，何奇正、郭铖浩同学会分享自己的工作，时长约为一到两小时。

• 何奇正：More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

  何奇正是姚班2014级（计科40）毕业生，现为UIUC博士三年级。目前主要的研究方向是计算几何算法。本次seminar他将介绍关于一些几何物体（正方形、圆、三维半空间）的集合覆盖问题的近似算法，并在亚线性时间内支持动态修改。此前的已知结果仅对单位正方形成立，而这项工作继续填补了动态几何集合覆盖问题的空白。算法的核心思想为猜测答案大小并分别设计算法，使用到了乘法权重调整、平面分割定理、随机抽样以及许多几何数据结构等技巧。有趣的是，基于这一动态数据结构，我们还可以顺便得到对于静态几何集合覆盖问题的最优O(n log n)时间近似算法。这项工作与导师Timothy M. Chan合作完成，即将发表于SoCG 2021会议。

  arxiv链接

• 郭铖浩： Generalizing Complex Hypothesis on Product Distributions

  郭铖浩是姚班2016级（计科60）毕业生，是MIT博士一年级在读。目前主要的研究方向是随机算法，smoothed analysis和信息论。这次seminar他将讨论乘积分布上的泛化误差问题。在传统的机器学习问题理论中，我们通常通过研究函数类的复杂度来估计泛化误差的上界。然而在需要学习的函数类复杂度过高，甚至难以计算复杂度的时候，这样的理论作用很小。实际上，如果真实分布满足一些特殊的条件（例如是乘积分布），那么我们可以得到与函数类复杂度独立的足够好的泛化误差上界。这次的talk将会涵盖一些这样的结果以及它们的应用。

  arxiv链接

• 【匿名提问】
• 【重复一遍时间地点】本周日（5月23日）下午1:00，六教6A102。点击此处进行时区转换

本周日（4月18日）下午1:30，学堂112，王世因、任瀚林同学会分享自己的工作，时长约为一到两小时。

• 王世因：Life @ Google

  王世因是姚班2016级（计科60）本科生，本科期间曾研究生物数据挖掘，现为Google东京办公室软件工程师。本次seminar她讲分享去年如何阴差阳错从学术界转入工业界、疫情期间在Google就职半年间的体验、Google的企业文化和远景。希望通过这次分享，让大家了解到本科毕业直接工作这条路径，扩展人生选择的空间。

• 任瀚林：Hardness of KT characterizes parallel cryptography

  任瀚林是姚班2016级（计科60）本科生，研究方向为计算复杂度理论。本次seminar他将分享去年年底与Rahul Santhanam教授合作的工作。他将介绍元复杂度（meta-complexity）和密码学中单向函数（one-way function）之间的联系。特别地，他会介绍一个叫做MKTP的问题的平均复杂度与“并行”单向函数（one-way function in NC0）的等价性。

• 【匿名提问】

• 【重复一遍时间地点】本周日（4月18日）下午1:30，学堂112 点击此处进行时区转换

本周日（4月11日）下午1:30，学堂112，陈胤伯、袁伟强同学会分享自己的工作，时长约为一到两小时。

• 陈胤伯：Learning Continuous Image Representation with Local Implicit Image Function

  陈胤伯是姚班2015级（计科50）毕业生，现为UCSD博士一年级，研究方向是deep learning。这次seminar他将介绍他最近CVPR oral的工作LIIF，一种能解码成任意分辨率的图片表示。

• 袁伟强：Log-rank and lifting for AND-functions

  袁伟强是姚班2017级（计科70）本科生，研究兴趣是理论计算机科学。本次seminar中他将介绍他于2020年春季前往UCSD访问与Shachar Lovett教授等人合作的成果。他们证明了一个布尔函数的AND决策树复杂度与它的Möbius稀疏度是多项式相关的（相差一个log n因子）。从这一定理能够直接得到两个关于通讯复杂度的重要结论（均相差一个log n因子）：AND-function的log-rank定理，以及AND-function的lifting定理。

• 【匿名提问】

• 【重复一遍时间地点】本周日（4月11日）下午1:30，学堂112 点击此处进行时区转换

本周六（3月27日）下午1:00，学堂112，乔明达、李嘉图、杨天祺同学会分享自己的工作，时长约为一到两小时。

• 乔明达：Selectivity and Calibration in Online Prediction

  乔明达是姚班2014级（计科40）毕业生，目前是斯坦福大学的三年级博士生。他的主要研究方向是机器学习理论，侧重于研究针对最坏情况数据的在线预测和学习算法的理论保证。这次seminar他将介绍有关在线预测问题的两个新角度：选择性预测（selective prediction）和校准误差（calibration error）。他还将分享这两个研究项目背后的一些经历与体会。

• 李嘉图&杨天祺：Towards better circuit lower bounds for explicit functions

  李嘉图和杨天祺是姚班2019级（计科92）本科生，目前的研究兴趣是计算复杂度理论中的电路复杂性和伪随机性。电路复杂性（circuit complexity）是复杂性理论中广为关注的问题。其中一个经典结论是大多数语言都需要指数级大小的电路才足以进行判定，但是该结论的证明是非构造性的。本次seminar他们将介绍此方面的近期工作：如何构造一个多项式时间可计算问题，使其不能被较小的电路所计算？

• 【匿名提问】

• 【重复一遍时间地点】本周六（3月27日）下午1:00，学堂112 点击此处进行时区转换

本周日（3月21日）下午1:00，学堂112，谢倩、唐一凡同学会分享自己的工作，时长约为一到两小时。

• 谢倩：Robust and Secure Routing For Queuing Networks and Internet of Vehicles

  谢倩是姚班2015级（计科50）毕业生，现为纽约大学博士二年级，研究方向是排队论相关的控制决策优化及在智能交通中的应用。这次 seminar 她将简单介绍如何结合排队论、博弈论、动态规划、马尔可夫决策过程来设计未知或有安全风险的环境下的控制策略，以及在signal-free intersection的应用。她还会分享她两次留学申请的经验和在运筹控制方向中摸索的感悟。

• 唐一凡：Efficient entanglement generation and detection of generalized stabilizer states

  唐一凡是姚班2017级（计科70）本科生，马雄峰老师课题组成员，大三时曾访问哈佛大学物理系Arthur Jaffe教授组，同时在清华大学丘成桐数学科学中心刘正伟教授指导下研究课题。唐一凡同学的研究领域是量子信息和量子计算，在纠缠探测和拓扑量子计算方向有所涉猎。本次seminar他将分享在马老师的指导下，与在读博士生张艺泓、周游博士合作的工作。广义稳定子态是量子信息处理中常见的一类态，该工作研究了广义稳定子态的纠缠如何产生与探测的问题，设计并优化了相应的纠缠验证，并对其实验测量复杂度和抗噪能力进行了分析。

• 【重复一遍时间地点】本周日（3月21日）下午1:00，学堂112 点击此处进行时区转换

本周日（3月14日）下午1:00，四教4101，彭雨翔、迟舒乘同学会分享自己的工作，时长约为一小时到一个半小时。

• 彭雨翔：Algebraic Reasoning of Quantum Programs

  彭雨翔是姚班2015级（计科50）校友，现于马里兰大学跟从伍骁迪教授，研究量子系统上的编程语言与软件设计。这次 seminar 他将介绍被去年疫情封锁在家期间与伍骁迪教授、应明生教授合作的工作，探讨如何使用代数方法对量子程序进行刻画及应用，以及一些简单的编程语言小科普。如果大家有兴趣的话，他还会分享分享做一个真·冷门方向的小体会。

• 迟舒乘：Differentiated nonblocking: a new progress condition and a matching queue algorithm

  迟舒乘是姚班2017级（计科70）本科生，研究方向是分布式计算中的并发数据结构、算法和 reliability，曾与多伦多大学的 Sam Toueg 教授、Vassos Hadzilacos 教授合作。这次 seminar 迟舒乘同学将介绍自己在多伦多大学交流期间的工作。对于分布式计算中的共享对象和数据结构，他们提出了一个新的 liveness requirement，以及一个符合条件的共享队列算法。相比于传统的共享队列算法，这个算法在公平性上表现出了显著的优越性。

• 【重复一遍时间地点】今天下午1:00，四教4101

今天下午1:00，学堂112教室，刘研绎、赵晟宇同学分享自己的工作，时长约1h。

• 刘研绎：On One-way Functions and Kolmogorov Complexity

  刘研绎是姚班2015级（计科50）毕业生，现为 Cornell 大学博士二年级，导师是 Rafael Pass 和 Elaine Shi，研究方向是密码学。这次 seminar 将介绍他和 Rafael Pass 在 FOCS2020 上发表的论文《On One-way Functions and Kolmogorov Complexity》。这篇文章建立了两大计算理论基本问题的等价性，分别关于 one-way function 和 t-time bounded Kolmogorov complexity，并由此提出了第一个可以刻画密码学中 private-key primitives 的自然问题。如果有机会（并且大家有兴趣）的话，刘研绎同学还会给大家分享分享他是如何误入密码学这个大坑的。

• 赵晟宇：Efficient GAN Training and Design

  赵晟宇是姚班2017级（计科70）本科生，大三时曾在 MIT 韩松实验室春研，也同时与朱俊彦合作。赵晟宇同学的研究方向是深度学习和计算机视觉。生成对抗网络（GAN）是深度学习近年来的研究热点之一，然而现有的生成对抗网络依赖于大量的训练样本和任务特异的网络结构，训练代价和设计成本都非常高昂。能否找到一种简单的训练算法有效减轻生成对抗网络对于大量数据的依赖？是否存在一种通用的网络结构能够跨越从图像生成到 image-to-image translation 不同任务之间的鸿沟？这次 seminar 他会结合 NeurIPS 和 ICLR 的工作（轻松愉快地）介绍以上两个问题的最新进展。

• ps：因为 speaker 的时间关系我们改在下午1点开始。这是本学期的最后一次seminar了，希望学弟学妹学长学姐多多支持！

今天下午4:00，学堂112教室，任瀚林、杨家齐同学分享自己的工作，时长约1h。

• 杨家齐：Linear Bandits with Limited Adaptivity

  杨家齐是姚班2017级（计科70）本科生，大三春季学期曾与周源教授合作，研究兴趣是理论计算机科学。线性老虎机问题是大规模在线学习的基本问题。但在大规模应用在线学习算法时，频繁调整算法的策略会带来不可承受的代价。这次演讲杨家齐同学会介绍策略调整次数受限的线性老虎机问题，以及在研究这一问题中建立的线性回归的随机试验设计理论。

• 任瀚林：Approximate Distance Oracles Subject to Multiple Vertex Failures

  任瀚林是姚班2016级（计科60）本科生，研究兴趣是算法与计算理论。给你一个 n 个节点的无向图，每次给定节点 s, t 和 d 个故障节点，询问从 s 到 t 不经过故障节点的最短路长度，允许有 1 + eps 的相对误差。你能设计一个怎样的高效数据结构？这次 seminar 任瀚林同学会介绍如何把询问时间做到 poly(log n, d, eps^{-1})。

• ps：这次是本学期的倒数第二次seminar了，在学堂下午4点，希望大家多多支持！有好吃的零食和饮料，欢迎学弟学妹学长学姐参加！

今天下午4:00，六教6A203教室，余文峻、吴晨玮同学分享自己的工作，时长约1h。

• 余文峻：Robust Shadow Estimation

  余文峻是姚班2017级（计科70）本科生，大二暑假曾与 Steven Flammia 教授有过合作，研究兴趣是量子计算中的噪声处理和 noisy intermediate-scale quantum 协议。这次 seminar 他会介绍如何构造在实际实验条件下对未知的量子态进行一定程度的估计的快速算法。

• 吴晨玮：(Beyond) Lazy Training for Over-parameterized Tensor Decomposition

  吴晨玮是姚班2014级（计科40）毕业生，大三时曾在 Jason D. Lee 组春研，现为杜克大学博士三年级，导师是鬲融教授（姚班2004级毕业生），研究方向是 deep learning theory。这次 seminar 他会介绍自己博士期间的一些工作，研究的是梯度下降算法在过参数化张量分解问题（over-parameterized tensor decomposition）上的收敛性分析。吴晨玮同学还会分享一下自己几年来与美国签证之间的爱恨情仇。

• ps：这次是本学期的倒数第二次seminar了，在学堂下午4点，希望大家多多支持！有好吃的零食和饮料，欢迎学弟学妹学长学姐参加！

今天下午4:00，学堂112教室，尹龙晖、吕凯风同学分享自己的工作，时长约1h。

• 尹龙晖：Algorithms, Properties, and Data Structures for Vertex k-Connectivity in Undirected Graphs

  尹龙晖是姚班2017级（计科70）本科生，大三时曾在密歇根大学的 Seth Pettie 组春研，研究图论问题。这次 seminar 他会介绍春研的一些工作，研究的是无向图中点k-连通性（vertex k-connectivity）相关的算法、性质和数据结构。

• 吕凯风：The Implicit Bias of Gradient Descent: Norm Minimization, Margin Maximization, and How to Go Beyond Them

  吕凯风是姚班2015级（计科50）毕业生，大三时曾在普林斯顿的 Sanjeev Arora 组暑研，之后一直在做 deep learning theory。这次 seminar 他会介绍一下自己近期的工作，研究的是在一些简单情形下用 gradient descent 算法训练出来的神经网络具有怎样的特殊性，以及这些特殊性可以如何帮助我们理解 deep learning。吕凯风同学还会稍微分享一下自己美国 F1 留学签证受阻一年多以来的故事。

• ps：因为speaker晚上有事我们这次仍然维持下午4点～有好吃的零食和饮料，欢迎学弟学妹学长学姐参加！

今天下午4:00，学堂112教室，龙耀为、陈治学同学分享自己的工作，时长约1h。

• 龙耀为：Planar Distance Oracles with Better Time-Space Tradeoffs

• 陈治学：Curriculum Learning with Pseudo Targets for Abstractive Sentence Summarization

• 注意时间和地点变动！有好吃的零食和饮料，欢迎学弟学妹学长学姐参加！

今天下午4:00，四教4101，洪文浩、郑书豪同学分享自己的工作，时长约1h。

• 洪文浩：On Computational Shortcuts for Information-Theoretic PIR

• 郑书豪：Efficient Data Reduction via Cluster-based Data Weighting

• 注意时间和地点变动！有好吃的零食和饮料，座位充足，欢迎学弟学妹学长学姐参加！

今晚7:00，四教4105，杨坤禾、竺涵林同学分享自己的工作，时长约1h。

• 杨坤禾：Q-learning with Logarithmic Regret

• 竺涵林：Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics and Graph Problems

• 注意时间和地点变动！有好吃的零食和饮料，座位充足，欢迎学弟学妹学长学姐参加！

今天下午4:00，六教6A201，徐明宽、武弘勋同学分享自己的工作，时长约1h。

• 徐明宽：Optimizations of Taichi Intermediate Representation

• 武弘勋：Good Contention Resolution Schemes for Matroid Cannot be Oblivious

• 注意时间和地点变动！有好吃的零食和饮料，座位充足，欢迎学弟学妹学长学姐参加！

今晚7:00，六教6A203，吕欣、陈俊锟同学分享自己的工作，时长约1h。

• 吕欣：Almost-Everywhere Circuit Lower Bounds from Nontrivial Derandomization

• 陈俊锟：Few-Shot Knowledge Graph Reasoning

• 注意地点变动！有好吃的零食和饮料，座位充足，欢迎学弟学妹（学长学姐）参加！同时欢迎大家报名/推荐别人报名分享自己的工作！

本周日（9.27）晚7:00，学堂112教室，翁文涛、于宸锴同学分享自己的工作，时长约1h。

• 翁文涛：Optimal Load Balancing in Bipartite Graphs

• 于宸锴：The Power of Predictions in Online Control

• 注意地点变动！有好吃的零食和饮料，座位充足，欢迎学弟学妹（学长学姐）参加！同时欢迎大家报名/推荐别人报名分享自己的工作！