Monotone Boolean Formulas can Approximate Monotone Linear Threshold Functions.
R. Servedio.
Discrete Applied Mathematics 142(1-3), 2004, pp. 181-187.


We show that any monotone linear threshold function on $n$ Boolean variables can be approximated to within any constant accuracy by a monotone Boolean formula of poly$(n)$ size.

Postscript or pdf .

Back to main papers page