Publication Details
Title: Sensitivity of Boolean Functions, Harmonic Analysis, and Circuit Complexity
Author: A. Bernasconi and B. Codenotti
Group: ICSI Technical Reports
Date: June 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-030.pdf
Overview:
We exploit the notion of sensitivity of Boolean functions to find complexity results. We first analyze the distribution of the average sensitivity over the set of all the Boolean functions, and show some applications of this analysis. We then use harmonic analysis on the cube to study how the average sensitivity of a Boolean function propagates if the function corresponds, e.g., to an oracle available to compute another function. We use this relation to prove that symmetric functions in AC^0 have exponentially decreasing average sensitivity.
Bibliographic Information:
ICSI Technical Report TR-93-030
Bibliographic Reference:
A. Bernasconi and B. Codenotti. Sensitivity of Boolean Functions, Harmonic Analysis, and Circuit Complexity. ICSI Technical Report TR-93-030, June 1993
Author: A. Bernasconi and B. Codenotti
Group: ICSI Technical Reports
Date: June 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-030.pdf
Overview:
We exploit the notion of sensitivity of Boolean functions to find complexity results. We first analyze the distribution of the average sensitivity over the set of all the Boolean functions, and show some applications of this analysis. We then use harmonic analysis on the cube to study how the average sensitivity of a Boolean function propagates if the function corresponds, e.g., to an oracle available to compute another function. We use this relation to prove that symmetric functions in AC^0 have exponentially decreasing average sensitivity.
Bibliographic Information:
ICSI Technical Report TR-93-030
Bibliographic Reference:
A. Bernasconi and B. Codenotti. Sensitivity of Boolean Functions, Harmonic Analysis, and Circuit Complexity. ICSI Technical Report TR-93-030, June 1993