一、会议简介

算法与计算理论是理论计算机科学的主要研究领域之一，是软件学科的基础研究内容。本次会议邀请了国内算法和计算领域的知名学者，围绕结构信息论、特性检测、量子算法、计数复杂性等专题，就最新优秀研究成果做学术报告，并与参会同行作深入的研讨，提高学术研究水平，促进学术发展与合作。

二、会议基本情况

1.主办单位（邀请人）：beat365在线体育官网，张鹏副教授。

2.会议时间：2021年10月11日9:00-16:10

3.会议方式：腾讯会议，会议号：104 606 628

会议二维码：

三、会议日程

四、专家报告

1.报告专家：李昂生

报告题目：信息科学的数学原理，I：信息基本定律

摘要：Shannon 1948年建立了通信的数学理论，完美地解决了信息传输的理论问题，开创了信息理论的研究。然而作为一个科学概念，而不仅仅是通信概念的信息的基本问题长期以来一直没有得到很好解决。严格地讲，熵是不确定性的量，信息是消除的不确定性，信息量是消除的不确定性的量。因此，信息是自然界和现实世界的基本概念，它是和数一样的基本概念。作为科学概念的信息有怎样的基本定律？在这一报告中，我讲介绍作为科学概念的信息的基本定律、信息科学的基本范式、信息科学的基本问题以及信息科学与包括机器学习、机器智能等在内的其它学科的关系。

简介：李昂生，北京航空航天大学教授，2003国家杰出青年基金获得者，2008中国科学院百人计划入选者。李昂生教授的主要研究方向为网络空间的信息与计算理论、结构信息论与信息科学原理，取得一系列原始创新成果。2016年，他提出结构信息的度量，创立结构息论，创建信息处理的数学理论。成果解决Brooks 2003年提出的计算机科学重大挑战性问题，并同时解决Shannon 1953年提出的建立信息的结构理论的重大科学问题。

2.报告专家：姚鹏晖

报告题目：Nonlocal games with noisy maximally entangled states are decidable

摘要：In this talk, we consider a special class of nonlocal games (G, psi)，where the players are allowed to share arbitrarily many copies of a given state psi. The value of the game (G, psi) is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states psi. In this talk, we prove that it is feasible to approximately compute the value of the game to an arbitrarily precision when the state psi is a noisy EPR state. In a recent breakthrough result, Ji, Natarajan, Vidick, Wright and Yuen showed that it is undecidable to approximate the values of nonlocal games to a constant precision, when the players preshare arbitrarily many copies of perfect maximally entangled states. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy.

简介：姚鹏晖，南京大学计算机科学与技术系副教授；本科毕业于华东师范大学数学系，博士毕业于新加坡国立大学量子技术中心（CQT），之后先后在荷兰国家数学与计算机中心（CWI）、加拿大滑铁卢大学量子计算研究所（IQC）、美国马里兰大学量子信息与计算机科学联合中心（QuICS）从事博士后研究工作。主要研究方向是计算复杂性、量子算法与量子信息论，在算法和通信复杂性上做出一系列重要成果。在理论计算机科学顶级会议STOC、FOCS和信息论顶级期刊IEEE Transaction on Information Theory上发表多篇论文，获得中组部国家高层次人才青年计划。

3.报告专家：彭攀

报告题目：Property Testing，First-Order Logic and Expander Graphs

摘要：Graph property testing is a framework for studying sampling-based graph algorithms. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph model. We show that any FO property that is defined by a formula with quantifier prefix∃*∀*is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix∀*∃* that is not testable. In the dense graph model, a similar picture is long known (Alon, Fisher, Krivelevich, Szegedy, Combinatoria 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs.

Building upon the above result, we resolve one open question by Goldreich and Ron (STOC 2009; SICOMP 2011) regarding the characterization of graph properties that have a proximity-oblivious tester (POT) in the bounded-degree graph model.

Joint work with Isolde Adler and Noleen Köhler.

简介：Pan Peng（彭攀）is a (Tenure-Track) Professor in the School of Computer Science and Technology at University of Science and Technology of China (USTC). His research interests lie on the intersection between theoretical computer science, network science and data science. He was a lecturer (assistant professor) at University of Sheffield, UK, and a postdoc researcher at TU Dortmund, Germany and University of Vienna, Austria. He got his Ph.D in the Institute of Software, Chinese Academy of Sciences in 2013 and received bachelor degree in Mathematics from Beijing Normal University in 2007.

4.报告专家：夏盟佶

报告题目：图子式与完美匹配的计算复杂性

摘要：图的类别显著地影响完美匹配数目问题的计算复杂性。经典的FKT算法和计数复杂性结果分别告诉我们：平面图的完美匹配数目问题可在多项式时间内计算，而一般图的完美匹配数目问题是#P难的。众所周知，平面图可以用禁止K5和K33图子式来定义。对其他图H，禁止图子式H，完美匹配的计算复杂性如何？将简述此问题的相关结果，直至论文Parameterizing the Permanent: Hardness for K8-minor-free graphs（arXiv 2108.12879）中的最新小结果。

简介：夏盟佶，中国科学院软件研究所研究员。2002年毕业于山东师范大学数学系，2008年在中科院软件所获得博士学位，之后在美国威斯康星大学研究助理，2009年回软件所工作至今，期间2012年底起的两年在德国马普所博士后。主要研究算法与计算复杂性中的计数复杂性，研究兴趣包括张量网络、图论等。

5.报告专家：潘祎诚

报告题目：An Information-theoretic Perspective of Hierarchical Clustering

摘要：A combinatorial cost function for hierarchical clustering was introduced by Dasgupta (2016). It has been generalized by Cohen-Addad et al. (2019) to a general form named admissible function. In this paper, we investigate hierarchical clustering from the information-theoretic perspective and formulate a new objective function. We also establish the relationship between these two perspectives. In algorithmic aspect, we get rid of the traditional top-down and bottom-up frameworks, and propose a new one to stratify the sparsest level of a cluster tree recursively in guide with our objective function. For practical use, our resulting cluster tree is not binary. Our algorithm called HCSE outputs a k-level cluster tree by a novel and interpretable mechanism to choose k automatically without any hyper-parameter. Our experimental results on synthetic datasets show that HCSE has a great advantage in finding the intrinsic number of hierarchies, and the results on real datasets show that HCSE also achieves competitive costs over the popular algorithms LOUVAIN and HLP.

简介：潘祎诚，北京航空航天大学，助理教授，研究兴趣包括算法、网络科学、机器学习、信息论。本次报告的内容是基于结构信息论的高维结构熵计算问题。结构信息论是报告人在网络结构分析领域的原创性理论，从图层谱结构的角度解决了图灵奖获得者Brooks在2003年提出的如何度量嵌入在复杂系统结构中的信息这一重要问题。该理论目前在生物、医学、金融、图像等领域已取得广泛应用。