Speaker: Nikolaos Kalampalikis (Master's Student, WPI)
Title: A graph theoretic proof for the Sensitivity Conjecture
Abstract: The Sensitivity Conjecture has been important problem in theoretical computer science. In this presentation, we will go over Huang's proof of showing that every (2n-1 +1)-vertex induced subgraph of the n-dimensional cube graph has maximum degree of at least √n. As a direct consequence we will show that sensitivity and degree of a boolean function are polynomially related.