Geodesic
Threshold Circuits Detecting Global Patterns in Two-dimensional Maps
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015) , Tome 20 (2016) no. 1, pp. 115-131.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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).
DOI : 10.7155/jgaa.00387
Keywords: neural networks, threshold circuits, graph drawing 
@article{JGAA_2016_20_1_a6,
     author = {Kei Uchizawa and Daiki Yashima and Xiao Zhou},
     title = {Threshold {Circuits} {Detecting} {Global} {Patterns} in {Two-dimensional} {Maps}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {115--131},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2016},
     doi = {10.7155/jgaa.00387},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00387/}
}
TY  - JOUR
AU  - Kei Uchizawa
AU  - Daiki Yashima
AU  - Xiao Zhou
TI  - Threshold Circuits Detecting Global Patterns in Two-dimensional Maps
JO  - Journal of Graph Algorithms and Applications
PY  - 2016
SP  - 115
EP  - 131
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00387/
DO  - 10.7155/jgaa.00387
LA  - en
ID  - JGAA_2016_20_1_a6
ER  - 
%0 Journal Article
%A Kei Uchizawa
%A Daiki Yashima
%A Xiao Zhou
%T Threshold Circuits Detecting Global Patterns in Two-dimensional Maps
%J Journal of Graph Algorithms and Applications
%D 2016
%P 115-131
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00387/
%R 10.7155/jgaa.00387
%G en
%F JGAA_2016_20_1_a6
Kei Uchizawa; Daiki Yashima; Xiao Zhou. Threshold Circuits Detecting Global Patterns in Two-dimensional Maps. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation  (WALCOM 2015)
					, Tome 20 (2016) no. 1, pp. 115-131. doi : 10.7155/jgaa.00387. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00387/

Cité par Sources :