Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-143 | 31st August 2015 06:11

The Average Sensitivity of Bounded-Depth Formulas

RSS-Feed




TR15-143
Authors: Benjamin Rossman
Publication: 31st August 2015 13:58
Downloads: 1009
Keywords: 


Abstract:

We show that unbounded fan-in boolean formulas of depth $d+1$ and size $s$ have average sensitivity $O(\frac{1}{d}\log s)^d$. In particular, this gives a tight $2^{\Omega(d(n^{1/d}-1))}$ lower bound on the size of depth $d+1$ formulas computing the PARITY function. These results strengthen the corresponding $2^{\Omega(n^{1/d})}$ and $O(\log s)^d$ bounds for circuits due to HÃ¥stad (1986) and Boppana (1997). Our proof technique studies a random process where the Switching Lemma is applied to formulas in an efficient manner.



ISSN 1433-8092 | Imprint