首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）于2020年8月17日-22日在线上举行，主题为“理论计算机科学领域的最新进展与焦点问题”，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

　　8月20日，中国科学院计算技术研究所的孙晓明研究员受邀带来题为《决策树复杂性中的一些开放问题（Some Open Problems in Decision Tree Complexity）》的主题报告，介绍了理论计算机中经典的决策树模型的复杂性。报告由北京大学前沿计算研究中心讲席教授邓小铁主持。

　　孙老师首先指出决策树模型在计算机科学中十分常见，所有包含 if,else 或类似功能的程序本质上都可以展开为一棵二叉决策树，而决策树复杂性则考虑的是针对一个特定的问题，最坏情况下要经过多少次这样的二分判断才能得到最终的结果。

　　图论为研究决策树复杂性提供了一个很好的例子，给定一个图，我们想确定这个图是否满足一些在同构意义下成立的性质，例如该图是否连通。通过简单的尝试，我们可以发现必须要询问该图所有的边是否存在才能够判断该图连通与否，对应的方法是由匈牙利数学家 Lovasz 在1990年提出的 adversary method，即程序每次针对一个新的一条边是否存在的提问，总是回答不存在，除非这一回答会导致图不连通。由此，我们可以理解 evasive 的概念，即必须要询问所有变量（这里是图的边）才能决定的性质（这里是连通性）。

　　很多图论中的经典性质都类似的在最坏情况下需要询问所有的边才能得到，而 Evasiveness Conjecture 则是在询问是否所有的 和所有输入点都相关的、单调的图性质都需要在最坏情况下询问所有边是否存在才能判断（单调递增是指给 A 图任意增加边得到 B 图，则若 A 图满足性质，B 图必然满足性质，单调递减概念类似，单调是指单调递增或单调递减）。弱化的 Evasiveness Conjecture 则是将定义中的“所有边”更换成了 Ω(n^2)。目前，通过代数学、代数拓扑学的一系列手段，弱化的 Evasiveness Conjecture 已被证明。孙老师随后指出 Evasiveness Conjecture 可以扩展到带随机性的决策树与量子决策树，并且量子决策树的类似的弱化版 Evasiveness Conjecture 已基于黄皓教授证明 sensitivity conjecture 的方法于今年被证明。

　　由此，孙老师自然地引出了一系列理论计算机中常见的复杂性模型，如 sensitivity，block sensitivity，degree，而 sensitivity conjecture 的证明则使这些在不同背景下提出的复杂度模型全部能在多项式范围内互相 bound。

　　报告的最后，孙老师指出了一些与 degree complexity 相关的公开问题，并且指出黄皓教授证明 sensitivity conjecture 的技术很可能能用来解决更多的问题，表达了他对复杂度领域未来的期望。