Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015)
Threshold Circuits Detecting Global Patterns in Two-dimensional Maps
Kei Uchizawa, Daiki Yashima, and Xiao Zhou
Vol. 20, no. 1, pp. 115-131, 2016. Regular paper.
Abstract In this paper, we consider a biologically-inspired Boolean function PnD that models a simple task of detecting global spatial patterns on a two-dimensional map. We prove that PnD is computable by a threshold circuit of size (i.e., number of gates) O(√n logn), which is an improvement on the previous upper bound O(n), while our circuit has larger depth O(√n) and total wire length O(n log2 n). Moreover, we demonstrate that the size of our circuit is nearly optimal up to a logarithmic factor: we show that any threshold circuit computing PnD has size Ω(√n/logn).
Submitted: March 2015.
Reviewed: July 2015.
Revised: July 2015.
Accepted: September 2015.
Final: January 2016.
Published: February 2016.
Communicated by M. Sohel Rahman and Etsuj Tomita
article (PDF)