Skip to main content

Mathematical Sciences Discrete Mathematics Seminar: "A graph theoretic proof for the Sensitivity Conjecture" Nikolaos Kalampalikis (Master's Student, WPI)

Tuesday, December 07, 2021
3:00 pm to 3:50 pm
Floor/Room #: 

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.