2019-08-06 | 黄皓:A proof of the Sensitivity Conjecture

2019-08-06   

Abstract

In the n-dimensional hypercube graph, one can easily choose half of the vertices such that they induce an empty graph. However, having even just one more vertex would cause the induced subgraph to contain a vertex of degree at least \sqrt{n}. This result is best possible, and improves a logarithmic lower bound shown by Chung, Furedi, Graham and Seymour in 1988. In this talk we will discuss a very short algebraic proof of it.

As a direct corollary of this purely combinatorial result, the sensitivity and degree of every boolean function are polynomially related. This solves an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy. 

 

Time

86日(星期二)  14:00--15:00

 

Speaker

黄皓,2007年本科毕业于北京大学,博士就读于美国加州大学洛杉矶分校,师从国际著名数学家Benny Sudakov教授,于2012年获得博士学位,2012-2014年受邀访问美国普林斯顿高等研究院,现担任美国艾默里大学数学系助理教授。其主要研究领域包括极值组合、图论及理论计算机。已经在JCTB, JCTA, Combinatorica, SIAM J. Discrete Math等国际著名期刊上发表及接受发表论文20余篇。作为被邀请人,在四十多个国际会议上做邀请报告,此外,曾多次组织国际会议, 现为亚特兰大组合和图论讲座系列的主办者之一。

 

Venue

信息管理与工程学院308

上海财经大学(第三教学楼西侧)

上海市杨浦区武东路100