Brandeis-Harvard-MIT-Northeastern Joint Mathematics Colloquium

Thursday, October 24, 2019 at 4:30pm to 5:30pm

2-190

Hao Huang (Emory University)

Title: “A proof of the Sensitivity Conjecture”

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. 

Reception in 2-290 at 4:00PM

Event Type

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By School

School of Science

Department
Department of Mathematics
Add to my calendar

Recent Activity