On the Shrinkage Exponent for Read-Once Formulae
(Citations: 2)
Abstract: We prove that the size of any read-once de Morgan formula reduces in averageby a factor of at least p o(1)when all but a fraction p of the input variables arerandomly assigned to f0; 1g (here * ) 1= log 2 (5 1) 3:27). This resolves in thearmative a conjecture of Paterson and Zwick. The bound is shown to be tight upto a polylogarithmic factor for all p n.