2015 | OriginalPaper | Buchkapitel
Threshold Circuits for Global Patterns in 2-Dimensional Maps
Autoren: Kei Uchizawa, Daiki Yashima, Xiao Zhou
Verlag: Springer International Publishing
In this paper, we consider a biologically-inspired Boolean function, called
$P^n_D$
, which models a task for detecting specific global spatial arrangements of local visual patterns on a 2-dimensional map. We prove that
$P^n_D$
is computable by a threshold circuit of size
$O(\sqrt{n}\log n)$
, which is improvement on the previous upper bound
O
(
n
). We also show that the size of our circuit is almost optimal up to logarithmic factor: we show that any threshold circuit computing
$P^n_D$
needs size
$\Omega(\sqrt{n}/\log n)$
.
