Classes of feedforward neural networks and their circuit complexity

John S. Shawe-Taylor, Martin H.G. Anthony, Walter Kern

Research output: Contribution to journalArticleAcademic

10 Citations (Scopus)
144 Downloads (Pure)


This paper aims to place neural networks in the context of boolean circuit complexity. We define appropriate classes of feedforward neural networks with specified fan-in, accuracy of computation and depth and using techniques of communication complexity proceed to show that the classes fit into a well-studied hierarchy of boolean circuits. Results cover both classes of sigmoid activation function networks and linear threshold networks. This provides a much needed theoretical basis for the study of the computational power of feedforward neural networks.
Original languageUndefined
Pages (from-to)971-977
JournalNeural networks
Issue number6
Publication statusPublished - 1992


  • IR-57459

Cite this