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.
No takes yet. Share an insight, caveat, or question.
Ravi B. Boppana (1997) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: