December 12, 2017 Theory Seminar 4:00 pm, CS 140

The Sensitivity of a Function

Samuel Schlesinger

Abstract: The Sensitivity of a function f at a point x is the number of Hamming neighbors, y, of x, such that f(y) does not equal f(x). It has been shown that any function with low sensitivity can be computed by a small circuit and that small circuits have low sensitivity. I will discuss two papers,"The Average Sensitivity of Bounded Depth Circuits" by Ravi Boppana and "Smooth Functions are Easy: Efficient Algorithms for Low Sensitivity Functions" by Widgerson et. al., circuits have low sensitivity.