BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UIC
BEGIN:VEVENT
UID:2019092109383820190913T15000020190913T1550005d86985e818fe@uic.edu
CATEGORIES:MEETING
STATUS:TENTATIVE
DTSTAMP:20190920T075056
DTSTART:20190913T150000
DTEND:20190913T155000
SUMMARY:Departmental Colloquium: A proof of the sensitivity conjecture, by Hao Huang
DESCRIPTION:Hao Huang (Emory): A proof of the sensitivity conjecture 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. Please click here to make changes to, or delete, this seminar announcement.
LOCATION:636 SEO Chicago IL
CLASS:PRIVATE
END:VEVENT
END:VCALENDAR