Directed vs. undirected monotone contact networks for threshold functions

Halldorsson, M. M. ; Radhakrishnan, J. ; Subrahmanyam, K. V. (1993) Directed vs. undirected monotone contact networks for threshold functions Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993 . pp. 604-613.

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...

Related URL: http://dx.doi.org/10.1109/SFCS.1993.366826

Abstract

We consider the problem of computing threshold functions using directed and undirected monotone contact networks. Our main results are the following. First, we show that there exist directed monotone contact networks that compute Tkn, 2<k<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 Ω(knlog (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(k3.99nlog n). Second, we show a lower bound of O(nlogloglog n) on the size of undirected monotone contact networks computing Tn-1n, 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.

Item Type:Article
Source:Copyright of this article belongs to Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993.
ID Code:89530
Deposited On:27 Apr 2012 14:16
Last Modified:27 Apr 2012 14:16

Repository Staff Only: item control page