DIMACS - Graduate Student Combinatorics Seminar

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


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.

See: http://www.math.rutgers.edu/~ajr224/GCS.html