The Average Sensitivity of Bounded-Depth Formulas
The Average Sensitivity of Bounded-Depth Formulas
复制标题
有界深度公式的平均灵敏度
DOI：
10.1007/s00037-017-0156-0
复制
发表时间：
2015
影响因子：
1.4
通讯作者：
Benjamin Rossman
中科院分区：
文献类型：
--
作者：
Benjamin Rossman
We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity O(1dlogs)d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${O(\frac{1}{d} \log s)^d}$$\end{document}. In particular, this gives a tight 2Ω(d(n1/d-1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\Omega(d(n^{1/d}-1))}}$$\end{document} lower bound on the size of depth d + 1 formulas computing the parity function. These results strengthen the corresponding 2Ω(n1/d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\Omega(n^{1/d})}}$$\end{document} and O(logs)d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${O(\log s)^d}$$\end{document} bounds for circuits due to Håstad (Proceedings of the 18th annual ACM symposium on theory of computing, ACM, New York, 1986) and Boppana (Inf Process Lett 63(5): 257–261, 1997). Our proof technique studies a random process where the switching lemma is applied to formulas in an efficient manner.
We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity O(1dlogs)d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${O(\frac{1}{d} \log s)^d}$$\end{document}. In particular, this gives a tight 2Ω(d(n1/d-1))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\Omega(d(n^{1/d}-1))}}$$\end{document} lower bound on the size of depth d + 1 formulas computing the parity function. These results strengthen the corresponding 2Ω(n1/d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\Omega(n^{1/d})}}$$\end{document} and O(logs)d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${O(\log s)^d}$$\end{document} bounds for circuits due to Håstad (Proceedings of the 18th annual ACM symposium on theory of computing, ACM, New York, 1986) and Boppana (Inf Process Lett 63(5): 257–261, 1997). Our proof technique studies a random process where the switching lemma is applied to formulas in an efficient manner.