Directed monotone contact networks for threshold functions

Abstract

In this note we consider the problem of computing threshold functions using directed monotone contact networks. We give constructions of monotone contact networks of size (k - 1)(n - k + 2) [log(n - k + 2)] computing Tⁿ_k , for 2 ≤ k ≤ n - 1. Our upper bound is close to the Ω(kn log(n/(k-1))) lower bound for small thresholds and the k(n-k+1) lower bound for large thresholds. Our networks are described explicitly; we do not use probabilistic existence arguments.