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.

孙晓明，现任中科院计算所研究员，2005年毕业于清华大学，获博士学位。曾任清华大学高等研究院助理研究员、副研究员。入选中组部万人计划（青年拔尖人才），获基金委首批优秀青年基金资助，曾获中国密码学会优秀青年奖。
他的主要研究方向为社会网络与博弈论相关的算法研究、量子计算、通信复杂性、判定树复杂度、组合数学。目前担任ACM China Magazine编委, Journal of Computer Science and Technology杂志编委， Math Reviews评论员等。