USING AMPLIFICATION TO COMPUTE MAJORITY WITH SMALL MAJORITY GATES

In this paper, we consider the formula complexity of the majority func tion over a basis consisting only of small (bounded-size) majority gat es. Using Valiant's amplification technique, we show that there is a f ormula of size O(n(4.29)) when only the gate M-3 (the majority gate on three inputs) is used. Then, based on a result of Boppana, we show th at not only is our result optimal with respect to the amplification te chnique, there is no smaller formula over the basis of all monotone 3- input functions (again with respect to amplification). Finally, we sho w that no better bounds are possible even with respect to more general input distributions. In particular, we show that it is not possible t o use amplification to ''bootstrap'', that is, use smaller majority fu nctions in the initial distribution to find an optimal formula for a l arger majority function.