Amplification of Bounded Depth Monotone Read-Once Boolean Formulae
Qian Ping Gu, Akira Maruoka · SIAM Journal on Computing · 1991
Let f be a Boolean function from $\{0,1\}^n$ to $\{0,1\}$. The amplification function $A_f $ of f from $[0,1]$ to $[0,1]$ is defined as $A_f (p) = \Pr [f({\bf X}_1 , \cdots ,{\bf X}_n ) = 1]$, where ${\bf X}_1 , \cdots ,{\bf X}_n $ are independent random variables with $\Pr [X_i = 1] = p$ for $1 \leqq i \leqq n$. f is said to amplify $(p,q)$ to $(p',q')$ if and only if $A_f (p) \leqq p'$ and $A_f (q) \geqq q'$. Let $\Sigma _d \cup \Pi _d $ be a family of monotone Boolean formulae with alternating d levels of AND gates and OR gates each having the same number of fan-ins. A Boolean formula is said to be read once when each variable in the formula occurs at most once. In this paper it is proven that the size of monotone read-once formulae in $\Sigma _d \cup \Pi _d $ that amplify $(p,p + 1 / m)$ to $(p',p' + 1 / c)$ is $\exp (\theta ((d - m)(m / c)^{1 / (d - 1)} ))$ under certain conditions.