Title: You Really Need to Be a Little Less Sensitive: Sensitivity Measures on the Boolean Cube
Speaker: John Chiarelli, Rutgers University
Date: Wednesday, October 12, 2016 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The study of Boolean functions is integral to both discrete math and computer science; one particular recurring question in dealing with them is quantifying how much of an impact changing some of the inputs of a given function can have on the output. In this talk, I will go over several major ways in which we perform such a quantification - sensitivity, block sensitivity, certificate complexity, decision tree depth, and tree sensitivity. I will also outline the relationships between these measures, both proven and conjectured.