Threshold Circuits Detecting Global Patterns in Two-dimensional Maps

Abstract

In this paper, we consider a biologically-inspired Boolean function Pⁿ_D that models a simple task of detecting global spatial patterns on a two-dimensional map. We prove that Pⁿ_D 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 log² 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 Pⁿ_D has size Ω(√n/logn).