Amplification and Percolat ion
Moshe Dubiner, Uri Zwick · 1992
Moore and Shannon had shown that relays with arbitrarily high reliability can be built from relays with arbitrarily poor reliability. Valiant used similar methods to construct monotone read-once formulae of size O(n ff+2 ) (where ff = log p 5\\Gamma1 2 ' 3:27) that amplify (/ \\Gamma 1 n ; / + 1 n ) (where / = p 5\\Gamma1 2 ' 0:62) to (2 \\Gamman ; 1 \\Gamma 2 \\Gamman ) and deduced as a consequence the existence of monotone formulae of the same size that compute the majority of n bits. Boppana had shown that any monotone read-once formula that amplifies (p \\Gamma 1 n ; p + 1 n ) to ( 1 4 ; 3 4 ) (where 0 ! p ! 1 is constant) has size of at least\\Omega\\Gamma n ff ) and that any monotone, not necessarily read-once, contact network (and in particular any monotone formula) that amplifies ( 1 4 ; 3 4 ) to (2 \\Gamman ; 1 \\Gamma 2 \\Gamman ) has size of at least \\Omega\\Gamma n 2 ). We extend Boppana's results in two ways. We first show that his two lower bounds...