Monotone Boolean formulas can approximate monotone linear threshold functions

摘要

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.