Some open problems in decision tree complexity

主讲人 Speaker:孙晓明
时间 Time: 周五16:30-17:30,2019-11-1
地点 Venue:清华大学近春园西楼三层报告厅

摘要 Abstract

Decision tree is a simple but important computational model for Boolean functions. Decision tree complexity has been widely studied and become an important subarea in computational complexity. In this talk I will give an introduction of the basic concepts and models in decision tree complexity. I will list some open problems and survey their recent progress, including Hao Huang's proof of sensitivity conjecture.

报告人简介 Profile

他的主要研究方向为社会网络与博弈论相关的算法研究、量子计算、通信复杂性、判定树复杂度、组合数学。目前担任ACM China Magazine编委, Journal of Computer Science and Technology杂志编委, Math Reviews评论员等。