Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:1, 153-166
Volume 25, No 1, 2018, P. 120-141
UDC 519.7
I. S. Sergeev
Rectifier circuits of bounded depth
Abstract:
Asymptotically tight bounds are obtained for the complexity of computation of the classesof (m,n)-matrices with entries from the set 0,1,…,q−1 by rectifier circuits of boundeddepth d, under some relations between m, n, and q. In the most important case of q=2, it is shown that the asymptotics of the complexity of Boolean (m,n)-matrices, log n=o(m),log m=o(n), is achieved for the circuits of depth 3.
Illustr. 1, bibliogr. 11.
Keywords: rectifier circuit, complexity, depth.
DOI: 10.17377/daio.2018.25.577
Igor S. Sergeev 1
1. FSUE “RDI ‘Kvant’ ”,
15 Chetvyortyi Likhachyovskii Lane, 125438 Moscow, Russia
e-mail: isserg@gmail.com
Received 19 April 2017
Revised 4 September 2017
References
[1] S. B. Gashkov and V. V. Kochergin, On addition chains of vectors, gate circuits, and the complexity of computations of powers, in Metody diskretnogo analiza v teorii grafov i slozhnosti (Methods of Discrete Analysis in Graph Theory and Complexity), Vol. 52, pp. 22–40, Izd. Inst. Mat., Novosibirsk, 1992. Translated in Sib. Adv. Math., 4, No. 4, 1–16, 1994.[2] S. B. Gashkov and I. S. Sergeev, An application of the method of additive chains to inversion in finite fields, Diskretn. Mat., 18, No. 4, 56–72, 2006. Translated in Discrete Math. Appl., 16, No. 6, 601–618, 2006.
[3] V. V. Kochergin, On the complexity of calculating systems of monomials with restrictions on the powers of variables, Diskretn. Mat., 10, No. 3, 27–34, 1998. Translated in Discrete Math. Appl., 8, No. 4, 375–382, 1998.
[4] V. V. Kochergin, The theory of rectifier circuits (the present state), in Diskretnaya matematika i eyo prilozheniya (Discrete Mathematics and Its Applications), Vol. 7, pp. 23–40, Izd. IPM RAN, Moscow, 2013.
[5] O. B. Lupanov, On rectifier and switching-and-rectifier schemes, Dokl. Akad. Nauk SSSR, 111, No. 6, 1171–1174, 1956.
[6] E. I. Nechiporuk, Rectifier networks, Dokl. Akad. Nauk SSSR, 148, No. 1, 50–53, 1963. Translated in Sov. Phys., Dokl., 8, 5–7, 1963.
[7] E. I. Nechiporuk, On the topological principles of self-correction, in Problemy kibernetiki (Problems of Cybernetics), Vol. 21, pp. 5–102, Nauka, Moscow, 1969. Translated in Systems Theory Res., 21, 1–99, 1970.
[8] A. Brauer, On addition chains, Bull. AMS, 45, 736–739, 1939.
[9] S. Jukna and I. S. Sergeev, Complexity of linear Boolean operators, Found. Trends Theor. Comput. Sci., 9, No. 1, 1–123, 2013.
[10] N. Pippenger, The minimum number of edges in graphs with prescribed paths, Math. Syst. Theory, 12, 325–346, 1979.
[11] N. Pippenger, On the evaluation of powers and monomials, SIAM J. Comput., 9, No. 2, 230–250, 1980.
