Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

Parikshit Gopalan, Noam Nisan, Rocco A. Servedio +2

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure…