A SHORT PROOF OF A FOURIER THEOREM
Date
1995-10-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A theorem of Kahn, Kalai, and Linial [2] stated that the average
sensitivity of a Boolean function is equal to the weighted sum of
its Fourier power spectrum. The purpose of this note is to provide
a short proof of this result that is based on a cross correlation
Fourier identity. Furthermore we generalize this to product
distributions and derive an alternative proof of a theorem in [1].
Description
Keywords
Computer Science