Some open problems in decision tree complexity

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

摘要

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评论员等。
  • 联系我们
  • 北京市海淀区清华大学静斋
    丘成桐数学科学中心100084
  • +86-10-62773561 
  • +86-10-62789445 
  • ymsc@tsinghua.edu.cn
版权所有© 2018 丘成桐数学科学中心