Directed vs. Undirected Monotone Contact Networks for Threshold Functions

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

Jaikumar Radhakrishnan
Theoretical Computer Science Group, Tata Institute of Fundamental Research, Bombay, India 400 005.

Abstract: We consider the problem of computing threshold functions using directed and undirected monotone contact networks. Our main results are the following. We show that there exist directed monotone contact networks that compute thresh{n}{k}, 2leq k leq n-1, of size O(k(n-k+2)log(n-k+2)). This bound is almost optimal for small thresholds, since there exists an Omega(k n log(n/(k-1))) lower bound. Our networks are described explicitly; the previously best upper bound known, obtained from the undirected networks of Dubiner and Zwick, used non-constructive arguments and gave directed networks of size O(k^{3.99} n log n). We show a lower bound of Omega(n logloglog n) on the size of undirected monotone contact networks computing thresh{n}{n-1}, improving the 2(n-1) lower bound of Markov. Combined with our upper bound result, this shows that directed monotone contact networks compute some threshold functions more easily than undirected networks.