布尔函数的敏感度综述

主讲人:吴保峰(中科院信息工程研究所)
时间:2019年10月15日上午10:00   地点:N205

【摘要】理论计算机科学的一个重要研究领域是布尔函数的计算复杂性理论,其研究往往综合运用线性代数、调和分析、概率论、图论等多种数学工具。Sensitivity、block sensitivity、(classical / quantum / randomized) decision tree complexity、certificate complexity、real algebraic degree是度量布尔函数计算复杂性的几个基本指标,计算复杂性理论的一个核心问题是研究这些指标的关系,其中一个近30年的猜想是sensitivity与其它几个复杂性指标都是多项式相关的,这称为布尔函数的敏感度猜想。近期,美国埃默里大学的Hao Huang给出了该猜想一个非常精妙、简洁的证明(论文即将在Ann. Math.发表)。本报告将对该猜想及Huang的证明过程进行介绍,并简介T. Tao对Huang的证明中一个关键矩阵的代数解释及D.Knuth对证明过程的进一步简化。

 

【报告人介绍】吴保峰,本科毕业于山东大学数学学院,2008年开始在中科院数学与系统科学研究院数学机械化实验室攻读博士学位,2013年博士毕业后进入中科院信息工程研究所信息安全国家重点实验室从事博士后研究,之后留所工作,现为信工所副研究员、硕士生导师。主要从事密码数学理论、密码函数相关领域研究,在Finite Fields and Their Applications、Discrete Applied Mathematics、ISIT等国际期刊或会议发表论文多篇,主持或参与国家自然科学基金面上项目、青年基金、专项基金以及军队密码合作基金等科研项目十余项。