Some open problems in decision tree complexity

Speaker:Sun Xiaoming
Time: Fri 16:30-17:30,2019-11-1
Venue:Lecture Hall, Jin Chun Yuan West Bldg.


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.


Sun Xiaoming is working as Professor at the Institute of Computing Technology, Chinese Academy of Sciences at present. He graduated from Tsinghua University in 2005 with a PhD, and was an assistant Professor of institute for advanced study of Tsinghua University.
He was selected to the national ten thousand talents program, supported by the first batch of outstanding youth fund of the fund committee, and won the outstanding youth award of China cryptography society.
His research interests include algorithms related to social networks and game theory, quantum computing, communication complexity and so on.
Currently, he is the editorial board member of ACM China Magazine, Journal of Computer Science and Technology, commentator of Math Reviews.