The average sensitivity of bounded-depth circuits
Ravi B. Boppana · Information Processing Letters · 1997
The average sensitivity of a Boolean circuit is the expected number of input bits that, when flipped, change the output of the circuit, starting with a random input setting. We show that unbounded-fanin circuits of depth d and size s have average sensitivity O(log s)d−1. This bound is asymptotically tight.