Classes of feedforward neural networks and their circuit complexity

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

Research output: Contribution to journalArticleAcademic

9 Citations (Scopus)
110 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