AbstractWe survey some of the central results in the complexity theory of discrete neural networks, with pointers to the literature. Our main emphasis is on the computational power of various acyclic and cyclic network models, but we also discuss briefly the complexity aspects of synthesizing networks from examples of their behavior.
Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation -- neural networks, circuits; F.1.3 [Computation by Abstract Devices]: Complexity Classes -- complexity hierarchies
Selected papers that cite this one
- Alexis Maciel and Denis Thérien. Efficient threshold circuits for power series. Accepted for publication in Information and Computation. Final manuscript received for publication August 10, 1998, 1998.
- Pekka Orponen. Computing with truly asynchronous threshold logic networks. Theoretical Computer Science, 174(1-2):123-136, 15 March 1997.
- Ji\v{r}í \v{S}íma and Ji\v{r}í Wiedermann. Theory of neuromata. Journal of the ACM, 45(1):155-178, January 1998.
Selected references
- Noga Alon, A. K. Dewdney, and Teunis J. Ott. Efficient simulation of finite automata by neural nets. Journal of the ACM, 38(2):495-514, April 1991.
- J. L. Balcázar, J. Díaz, and J. Gabarró On characterizations of the class PSPACE/poly. Theoretical Computer Science, 52(3):251-267, 1987.
- Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, April 1984.
- Mikael Goldmann and Marek Karpinski. Simulating threshold circuits by majority circuits. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 551-560, San Diego, California, 16-18 May 1993.
- E. Goles Ch. and J. Olivos A. The convergence of symmetric threshold automata. Information and Control, 51(2):98-104, November 1981.
- András Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, and György Turán. Threshold circuits of bounded depth. Journal of Computer and System Sciences, 46(2):129-154, April 1993.
- András Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, and György Turán. Threshold circuits of bounded depth. In 28th Annual Symposium on Foundations of Computer Science, pages 99-110, Los Angeles, California, 12-14 October 1987. IEEE.
- Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 302-309, Los Angeles, California, 28-30 April 1980.
- Michael Kearns and Leslie Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1):67-95, January 1994.
- Michael Kearns and Leslie G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 433-444, Seattle, Washington, 15-17 May 1989.
- Wolfgang Maass. Bounds for the computational power and learning complexity of analog neural nets (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 335-344, San Diego, California, 16-18 May 1993.
- Wolfgang Maass, Georg Schnitger, and Eduardo D. Sontag. On the computational power of sigmoid versus Boolean threshold circuits. In 32nd Annual Symposium on Foundations of Computer Science, pages 767-776, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- John H. Reif and Stephen R. Tate. On threshold circuits and polynomial computation. SIAM Journal on Computing, 21(5):896-908, October 1992.
- Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing, 20(1):56-87, February 1991.
- Eduardo D. Sontag. Feedforward nets for interpolation and classification. Journal of Computer and System Sciences, 45(1):20-48, August 1992.
- Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, pages 1-10, Portland, Oregon, 21-23 October 1985. IEEE.