学术报告
布尔函数的敏感度综述-吴保峰 副研究员（中国科学院信息工程研究所）
作者：
时间： 2020-10-20
阅读：
编码密码学术活动月系列活动五
题目：布尔函数的敏感度综述
报告人：吴保峰 副研究员（中国科学院信息工程研究所）
摘要：
理论计算机科学的一个重要研究领域是布尔函数的计算复杂性理论，其研究往往综合运用线性代数、调和分析、概率论、图论等多种数学工具。敏感度、分块敏感度、决策树复杂度、certificate复杂度、代数次数是度量布尔函数计算复杂性的几个基本指标，计算复杂性理论的一个核心问题是研究这些指标的关系，其中一个近30年的猜想是：敏感度与其它几个复杂性指标都是多项式相关的，这称为布尔函数的敏感度猜想。2019年美国埃默里大学的Hao Huang给出了该猜想一个非常精妙、简洁的证明（Ann. Math 190 (2019)）。本报告将对敏感度猜想的背景及Huang的证明过程进行介绍，并简介T. Tao、D.Knuth等学者对Huang的证明过程的进一步分析。
时间：2020年10月20日（周二） 下午14:30-15:30
地点：线上腾讯会议（会议号：635 261 049）
联系人：张俊
主办单位：首都师范大学77779193永利官网
首都师范大学交叉科学研究院
