Amplification of probabilistic boolean formulas
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The amplification of probabilistic Boolean formulas refers to combining independent copies of such formulas to reduce the error probability. Les Valiant used the amplification method to produce monotone Boolean formulas of size O(n5.3) for the majority function of n variables. In this paper we show that the amount of amplification that Valiant obtained is optimal. In addition, using the amplification method we give an O(k4.3 n log n) upper bound for the size of monotone formulas computing the kth threshold function of n variables.Keywords
This publication has 6 references indexed in Scilit:
- Short monotone formulae for the majority functionPublished by Elsevier ,2004
- A theorem on probabilistic constant depth ComputationsPublished by Association for Computing Machinery (ACM) ,1984
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- Two theorems on random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- InequalitiesPublished by Springer Nature ,1965
- Reliable circuits using less reliable relaysJournal of the Franklin Institute, 1956