The average sensitivity of bounded-depth circuits

✍ Scribed by Ravi B. Boppana

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 414 KB
• Volume: 63
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00131-2

✦ Synopsis

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 0( log s)~-'. This bound is asymptotically tight. @ 1997 Elsevier Science B.V.