FOCS Conference 1992 Conference Paper
Amplification and Percolation
- Moshe Dubiner
- Uri Zwick
The authors extend R. B. Boppana's results (1989) in two ways. They first show that his two lower bounds hold for general read-once formulae, not necessarily monotone, that may even include exclusive-or gates. They are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies (p-/sup 1///sub n/, p+/sup 1///sub n/) to (2/sup -n/, 1-2/sup -n/) has size of at least Omega (n/sup alpha +2/). This result does not follow from Boppana's arguments and it shows that the amount of amplification achieved by L. G. Valiant (1984) is the maximal achievable using read-once formulae. >