特邀报告


计数问题复杂度分类的一些近期进展


Jin-yi Cai
University of Wisconsin-Madison

摘要: 首先,我将概述计数问题的复杂性分类中的一些最新进展。这些进展在三个通用的框架中进行:图同态(或顶点模型),计数约束满足问题(#CSP)和Holant问题。 然后,我将描述一些复杂性二分定理,这些定理根据定义问题的特定约束函数将一大类计数问题中的每个问题分类为多项式时间可计算的问题或#P-hard问题。 同时我还将描述一些计数复杂性理论里的三分定理,它们可以描述一类在所述框架中所有以下形式的问题:这些问题是非平面#P难的,但是在平面情况都可以在多项式时间内解决。 这其中包括将Valiant的全息算法规约为Kasteleyn的平面图完美匹配算法等。该领域还有许多问题尚未得到解决。


最优机制设计:简洁度与鲁棒性


陆品燕
上海财经大学

摘要: 机制设计是微观经济学的中心主题。 在本次演讲中,我们重点探讨拍卖收益最大化。 我们将首先介绍著名的Myerson最优拍卖,并探讨Myerson所作的假设。 我们通过放宽假设促进机制设计问题,并讨论有关拍卖的简单性和鲁棒性的一些令人兴奋的进展。

本演讲基于以下共同作品:
•金耀南,陆品燕,齐琪,唐志皓,肖涛:匿名定价的微近视率。 第51届ACM计算理论年会. 金耀南,陆品燕,唐志皓,肖涛:简单机制中细微的收益差距。国际算法顶级会议 离散算法国际研讨会(SODA 2019)•贝小辉,尼克·格雷文,陆品燕,唐志皓:单项拍卖的相关性和稳健性分析。 离散算法国际研讨会(SODA 2019)•尼克·格雷文,陆品燕:带预算专利者分离式联合分布的相关性问题。离散算法国际研讨会(SODA 2019)


ALGORAND:真正的分布式区块链


Silvio Micali
Agorand Founder & MIT

摘要: 在区块链的理想模型中,区块链是不可篡改数据的数字化账本,每个人都可以读取它,每个人都可以在其上添加新数据。如果实施得当,这种模式将彻底改变社会学和传统经济学的运作方式。通过移除中介并引入新的信任机制,这种模型不仅会使传统交易(例如付款)更加有效,还会引发全新的交易范式(例如智能合约)。

不幸的是,目前的实现方法使得大多数区块链无法发挥其巨大潜力。我们将在报告中指出,区块链的理想模型是可以通过与当今非常不同的方法更加充分地实现的。


决策树复杂度方面的一些公开问题


孙晓明
中国科学院

摘要: 决策树是布尔函数的一种简单但重要的计算模型,而决策树复杂度是算法复杂度中被广泛研究的一个分支。 在本次讲座中,除了介绍决策树复杂度的一些基本概念和模型之外,我将主要介绍一些布尔函数的公开问题并概述它们的最新进展,其中包括布尔敏感度猜想和量子规避猜想的证明。


多智体学习


Jun Wang
University College London

摘要:多智能体学习在多种智能交互领域中不断涌现,这些场景中,不仅有智能体与(未知)环境的交互,还涉及智能体与智能体之间的交互。从控制一组自动驾驶车辆和无人机,到协调生产线中的合作式机器人,从优化分布式传感器网络与交通,到在竞争激烈的电子商务和金融市场中进行机器招标,多智能体学习的应用日益增多,上述只是简单举例。

然而,多智能体环境的不稳定性质,使得这一领域亟需新的理论把“交互”合理地引入学习过程。在本次报告中,我将对多智能体AI领域的最新理论和方法论做介绍,并重点聚焦于智能体之间的竞争、合作和通信。这次报告会以统一的视角,并行介绍涉及到的博弈论和机器学习的知识与研究工作。我将选取团队里近期的相关工作做介绍,包括平均场多智能体强化学习、随机势博弈以及纳什均衡上的博弈解变体。


用于模型检测的量子马尔可夫链


应明生
澳大利亚悉尼科技大学;中国科学院软件研究所;清华大学

摘要: 模型检测是计算机系统, 包括硬件和软件系统形式化验证的一项重要技术。它会自动检测系统是否具有所期望的属性。这些属性往往借助于时序逻辑来描述,其中无死锁,不变式,安全性及请求响应属性是典型属性。被检测系统在数学上常被建模为:有限状态自动机,转移系统,马尔可夫链及马尔可夫决策过程。

在本次讲座中,我将探讨为量子系统开发模型检测技术所面临的本质困难,这些困难是经典模型检测从未出现过的,然后回顾作者及其合作者在检测一般量子系统模型上所进行的一系列新研究,例如量子马尔可夫链,包括量子计算和通信系统硬件与软件。