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