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

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