Sensitivity of Boolean Functions, Harmonic Analysis, and Circuit Complexity
| Title | Sensitivity of Boolean Functions, Harmonic Analysis, and Circuit Complexity |
| Publication Type | Technical Report |
| Year of Publication | 1993 |
| Authors | Bernasconi, A., & Codenotti B. |
| Other Numbers | 818 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-030.pdf |
| Bibliographic Notes | ICSI Technical Report TR-93-030 |
| Abbreviated Authors | A. Bernasconi and B. Codenotti |
| ICSI Publication Type | Technical Report |