References and models cited by this paper

References and models that cite this paper

Ackley DH, Hinton GE, Sejnowski TJ (1985) A learning algorithm for Bolzmann machines. Cognitive Sci 9:147-69

Allender E (1989) A note on the power of threshold circuits Proc 30th Ann Symposium on Foundations of Computer Science :580-584

Alon N (1985) Asynchronous threshold networks Graphs And Combinatorics 1:305-310

Alon N, Bruck J (1994) Explicit construction of depth-2 majority circuits for comparison and addition SIAM J Discrete Math 7:1-8

Alon N, Dewdney AK, Ott TJ (1991) Efficient simulation of finite automata by neural nets J ACM 38:495-514

Balcazar JL, Diaz J, Gabarro J (1995) Structural complexity I (2nd ed)

Balcazar JL, Gavalda R, Siegelmann HT (1997) Computational power of neural networks: A characterization in terms of Kolmogorov complexity IEEE Trans Inform Theory 43:1175-1183

Balcazar JL, Hermo M (1998) The structure of logarithmic advice complexity classes Theoretical Computer Science 207:217-244

Barahona F (1982) On the computational complexity of I sing spin glass models J Phys A Math Gen 15:3241-3253

Ben-hur A, Siegelmann HT, Fishman S (2002) A theory of complexity for continuous time systems J Complex 18:51-86

Bertoni A, Campadelli P (1994) On the approximability of the energy function Proc 4th Intl Conf Artif Neural Networks :1157-1160

Bertoni A, Campadelli P, Gangai C, Posenato R (1997) Approximability of the ground state problem for certain I sing spin glasses J Complex 13:323-339

Bieche I, Maynard R, Rammal R, Uhry JP (1980) On the ground states of the frustration model of a spin glass by a matching method of graph theory J Phys A Math Gen 13:2553-2576

Bovet DP, Crescenzi P (1994) Introduction to the theory of complexity

Bruck J, Goodman JW (1988) A generalized convergence theorem for neural networks IEEE Trans Inform Theory 34:1089-1092

Casey M (1996) The dynamics of discrete-time computation, with application to recurrent neural networks and finite state machine extraction. Neural Comput 8:1135-78 [PubMed]

Chandra AK, Stockmeyer LJ, Vishkin U (1984) Constant depth reducibility SIAM J Comput 13:423-439

Cohen M, Grossberg S (1983) Absolute stability of global pattern formation and parallel memory storage by competitive neural network. Ieee Trans Smc 13:815-826

Cover T (1965) Geometric and statistical properties of systems of linear in-equalities with applications in pattern recognition IEEE Tran Elect Comput 14:326

Cover TM (1968) Capacity problems for linear machines Pattern Recognition, Kanal L, ed. pp.283

Dasgupta B, Schnitger G (1993) The power of approximating:A comparison of activation functions Advances In Neural Information Processing Systems, Hanson SJ:Cowan JD:Giles CL, ed. pp.615

DasGupta B, Schnitger G (1996) Analog versus discrete neural networks. Neural Comput 8:805-18 [PubMed]

Floreen P (1991) Worst-case convergence times for Hopfield memories. IEEE Trans Neural Netw 2:533-5 [Journal] [PubMed]

Floreen P, Orponen P (1989) On the computational complexity of analyzing Hopfield nets Complex Systems 3:577-587

Floreen P, Orponen P (1993) Attraction radii in Hopfield nets are hard to compute Neural Comput 5:812-821

Floreen P, Orponen P (1994) Complexity issues in discrete Hopfield networks Research Rep No A-1994-4, Department of Computer Science, University of Helsinki

Fogelman F, Goles E, Weisbuch G (1983) Transient length in sequential iterations of threshold functions Discrete Appl Math 6:95-98

Fogelman-Soulie F, Mejia C, Goles E, Martinez S (1989) Energy functions in neural networks with continuous local functions Complex Systems 3:269-293

Furst M, Saxe JB, Sipser M (1984) Parity, circuits and the polynomial-time hierarchy Math Systems Theory 17:13-27

Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness

Godbeer GH, Lipscomb J, Luby M (1988) On the computational complexity of finding stable state vectors in connectionist models (Hopfield nets) Tech Rep No 208-88

Goemans MX, Williamson DP (1995) Improved approximate algorithms for maximum cut and satisfiability problems using semidefinite programming J ACM 42:1115-1145

Goldmann M, Hastad J, Razborov A (1992) Majority gates vs. general weighted threshold gates Computational Complexity 2:277-300

Goldmann M, Karpinski M (1998) Simulating threshold circuits by majority circuits SIAM J Computing 27:230-246

Goldschlager LM, Parberry I (1986) On the construction of parallel computers from various bases of Boolean functions Theoretical Computer Science 43:43-48

Goles E (1985) Dynamics of positive automata networks Theoretical Computer Science 41:19-32

Goles E (1987) Lyapunov functions associated to automata networks Automata networks in computer science theory and applications, Fogelman-Soulie F:Robert Y:Tchuente M, ed. pp.58

Goles E, Martinez S (1989) Exponential transient classes of symmetric neural networks for synchronous and sequential updating Complex Systems 3:589-597

Goles E, Martinez S (1990) Neural and automata networks: Dynamical behaviorand applications

Goles E, Olivos J (1981) Comportement periodique des fonctions a seuilbinaires et applications Discrete Appl Math 3:93-105

Goles E, Olivos J (1981) The convergence of symmetric threshold automata Inform Control 51:98-104

Goles-chacc E, Fogelman-Soulie F, Pellegrin D (1985) Decreasing energy functions as a tool for studying threshold networks Discrete Appl Math 12:261-277

Gori M, Meer K (2002) A step towards a complexity theory for analog systems Mathematical Logic Quarterly 48:45-58

Hajnal A, Maass W, Pudlak P, Szegedy M, Turan G (1993) Threshold circuits of bounded depth J Comput System Sci 46:129-154

Haken A (1989) Connectionist networks that need exponential time to stabilize Unpublished manuscript, department of computer science, University of Toronto

Haken A, Luby M (1988) Steepest descent can take exponential time for symmetric connectionist networks Complex Systems 2:191-196

Hammer PL, Ibaraki T, Peled UN (1981) Threshold numbers and threshold completions Studies on graphs and discrete programming, Annals of Discrete Mathematics, Hansen P, ed. pp.125

Hartley R, Szu H (1987) A comparison of the computational power of neural network models Proc IEEE 1st Intl Conf Neural Networks :15-22

Hastad J (1989) Almost optimal lower bounds for small depth circuits Advances in computing research, randomness and computation, Michali S, ed. pp.143

Hastad J (1994) On the size of weights for threshold gates SIAM J Discrete Math 7:484-492

Hegedus T, Megiddo N (1996) On the geometric separability of Boolean functions Discrete Applied Mathematics 66:205-218

Hofmeister T (1994) Depth-efficient threshold circuits for arithmetic functions Theoretical advances in neural computation and learning, Roychowdhury VP:Siu KY:Orlitsky A, ed. pp.37

Hofmeister T, Hohberg W, Kohling S (1991) Some notes on threshold circuits, and multiplication in depth 4 Inform Process Lett 39:219-225

Hofmeister T, Pudlak P (1992) A proof that division is not in TC02 Res Rep No 447, Dortmund University

Hopfield JJ (1982) Neural networks and physical systems with emergent collective computational abilities. Proc Natl Acad Sci U S A 79:2554-8 [PubMed]

Hopfield JJ (1984) Neurons with graded response have collective computational properties like those of two-state neurons. Proc Natl Acad Sci U S A 81:3088-92 [PubMed]

Hopfield JJ, Tank DW (1985) "Neural" computation of decisions in optimization problems. Biol Cybern 52:141-52 [PubMed]

Horne BG, Hush DR (1994) On the node complexity of neural networks Neural Netw 7:1413-1426

Horne BG, Hush DR (1996) Bounds on the complexity of recurrent neural network implementations of finite state machines Neural Netw 9:243-252

Indyk P (1995) Optimal simulation of automata by neural nets Proc 12th Ann Symposium Theoretical Aspects of Computer Science 900:337-348

Irmatov AA (1996) Bounds for the number of threshold functions Discrete Math Appl 6:569-583

Johnson DS, Papadimitriou CH, Yannakakis M (1988) How easy is local search? J Computer And System Sci 37:79-100

Kahn J (1995) On the probability that a random 1 n matrix is singular J Am Math Soc 8:223-240

Kilian J, Siegelmann HT (1996) The dynamic universality of sigmoidal neural networks Inform Comput 128:48-56

Kleene SC (1956) Representation of events in nerve nets and finite automata Automata studies, Annals of mathematics studies, Shannon CE:McCarthy J, ed. pp.3

Kohonen T (2001) Self-Organizing Maps (3rd edition)

Koiran P (1994) Dynamics of discrete time, continuous state Hopfield networks Neural Comput 6:459-468

Koiran P (1996) A family of universal recurrent networks Theoretical Computer Science 168:473-480

Komlos J, Paturi R (1988) Convergence results in an associative memory model Neural Netw 1:239-250

Legenstein RA, Maass W (2001) Foundations for a circuit complexity theory of sensory processing Advances In Neural Information Processing Systems, Leen TK:Dietterich TG:Tresp V, ed. pp.259

Lepley M, Miller G (1983) Computational power for networks of threshold devices in asynchronous environment Tech Rep Department of Mathematics, MIT

Lipscomb J (1987) On the computational complexity of finding a connectionist models stable state vectors Unpublished masters thesis, Department of Computer Science, University of Toronto

Lupanov OB (1961) Implementing the algebra of logic functions in terms of bounded depth formulas in the basis Soviet Physics Doklady 6:107-108

Lupanov OB (1972) Circuits using threshold elements Soviet Physics Doklady 17:91-93

Maass W (1995) On the computational complexity of networks of spiking neurons Advances In Neural information Processing Systems, Tesauro G:Touretzky DS:Leen TK, ed. pp.183

Maass W (1996) On the computational power of noisy spiking neurons Advances In Neural Information Processing Systems, Touretzky D:Mozer MC:Hasselmo ME, ed. pp.211

Maass W (1996) Networks of spiking neurons: The third generation of neural network models Neural Networks 10:1659-1671

Maass W (1996) Lower bounds for the computational power of networks of spiking neurons Neural Comput 8:1-40

Maass W (1997) Fast sigmoidal networks via spiking neurons. Neural Comput 9:279-304 [PubMed]

Maass W (1997) Bounds for the computational power and learning complexity of analog neural nets SIAM J Computing 26:708-732

Maass W (2000) On the computational power of winner-take-all. Neural Comput 12:2519-35 [PubMed]

Maass W, Bishop CM (1999) Pulsed Neural Networks.

Maass W, Natschlager T (1997) Networks of spiking neurons can emulate arbitrary Hopfield nets in temporal coding Network: Computation In Neural Systems 8:355-372

Maass W, Natschläger T (2000) A model for fast analog computation based on unreliable synapses. Neural Comput 12:1679-704 [PubMed]

Maass W, Orponen P (1998) On the effect of analog noise in discrete-time analog computations Neural Comput 10:1071-1095

Maass W, Ruf B (1999) On computation with pulses Inform Comput 148:202-218

Maass W, Schmitt M (1999) On the complexity of learning for spiking neurons with temporal coding Inform Comput 153:26-46

Maass W, Schnitger G, Sontag ED (1991) On the computational power of sigmoid versus Boolean threshold circuits Proc 32nd Ann Symposium on Foundations of Computer Science :767-776

Maass W, Sontag ED (1999) Analog neural nets with gaussian or other common noise distribution cannot recognize arbitrary regular languages. Neural Comput 11:771-82 [PubMed]

Mahajan S, Ramesh H (1999) Derandomizing approximation algorithms based on semidefinite programming SIAM J Computing 28:1641-1663

Mceliece RJ, Posner EC, Rodemich ER, Venkatesh SS (1987) The capacity of the Hopfield associative memory IEEE Trans Inform Theory 33:461-482

Minsky M (1969) Perceptrons

Minsky ML (1967) Computation: Finite and infinite machines

Moore C (1998) Finite-dimensional analog computers: flows, maps, and recurrent neural networks Proc 1st Intl Conf Unconventional Models of Computation :59-71

Muroga S (1971) Threshold logic and its applications

Muroga S, Toda I, Takasu S (1961) Theory of majority decision elements Journal Of The Franklin Institute 271:376-418

Nechiporuk EI (1964) The synthesis of networks from threshold elements Problemy Kibernetiki 11:49-62

Oneil PE (1971) Hyperplane cuts of an n-cube Discrete Math 1:193-195

Orponen P (1994) Computational complexity of neural networks: A survey Nordic J Computing 1:94-110

Orponen P (1996) The computational power of discrete Hopfield nets with hidden units Neural Comput 8:403-415

Orponen P (1997) Computing with truly asynchronous threshold logic networks Theoretical Computer Science 174:123-136

Orponen P (1997) The computational power of continuous time neural networks Proc 24th Seminar on Current Trends in Theory and Practice of Informatics 1338:86-103

Orponen P (1997) A survey of continuous-time computation theory Advances in Algorithms, Languages, and Complexity, Du DZ:Ko KI, ed. pp.209

Orponen P (2000) An overview of the computational power of recurrent neural networks Proc 9th Finnish AI Conf Millennium of AI, Symposium on Theory, Hyotyniemi H, ed. pp.89

Papadimitriou CH (1994) Computational complexity

Parberry I (1990) A primer on the complexity theory of neural networks Formal techniques in artificial intelligence: A sourcebook, Studies in computer science and artificial intelligence, Banerji RB, ed. pp.217

Parberry I (1994) Circuit complexity and neural networks

Parberry I, Schnitger G (1989) Relating Boltzmann machines to conventional models of computation Neural Netw 2:56-67

Poljak S, Sura M (1983) On periodical behaviour in societies with symmetric influences Combinatorica 3:119-121

Porat S (1989) Stability and looping in connectionist models with asymmetric weights Biol Cybern 60:335-344

Powell MJD (1985) Radial basis functions for multivariable interpolation: A review Proc IMA Conf Algorithms for the Approximation of Functions and Data, Mason JC:Cox MG, ed. pp.143

Rabin MO (1963) Probabilistic automata Information And Control 6:230-245

Razborov AA (1992) On small depth threshold circuits Proc 3rd Scandinavian Workshop on Algorithm Theory, Nurmi O:Ukkonen E, ed. pp.42

Reif JH, Tate SR (1992) On threshold circuits and polynomial computations SIAM J Computing 21:896-908

ROSENBLATT F (1958) The perceptron: a probabilistic model for information storage and organization in the brain. Psychol Rev 65:386-408 [PubMed]

Roychowdhury VP, Siu KY, Orlitsky A (1994) Theoretical advances in neural computation and learning, Roychowdhury VP:Siu KY:Orlitsky A, ed.

Rumelhart DE, Hinton GE, Williams RJ (1986) Learning representations by back-propagating errors. Nature 323:533-536

Savage JE (1972) Computational work and time on finite machines J ACM 19:660-674

Savage JE (1998) Models of computation: Exploring the power of computing

Schaffer AA, Yannakakis M (1991) Simple local search problems that are hard to solve SIAM J Computing 20:56-87

Schlafli L (1901) Theorie der vielfachen Kontinuitat

Schmitt M (1998) On computing Boolean functions by a spiking neuron Ann Math Artif Intell 24:181-191

Schmitt M (2002) Descartes' rule of signs for radial basis function neural networks. Neural Comput 14:2997-3011 [Journal] [PubMed]

Siegelmann H, Sontag E (1995) On the computational power of neural nets Journal Of Computer And System Sciences 50:132-150

Siegelmann H, Sontag ED (1994) Analog computation via neural networks Theoretical Computer Science 131:331-360

Siegelmann HT (1994) Onthe computational power of probabilistic and faulty neural networks Proc 21st Intl Colloquium on Automata, Languages, and Programming, Abiteboul S:Shamir E, ed. pp.23

Siegelmann HT (1996) Recurrent neural networks and finite automata J Comput Intell 12:567-574

Siegelmann HT (1999) Neural networks and analog computation: Beyond the Turing limit

Siegelmann HT (1999) Stochastic analog networks and computational complexity J Complexity 15:451-475

Siegelmann HT, Roitershtein A, Ben-hur A (2000) Noisy neural networksand generalizations Advances In Neural Information Processing Systems, Solla SA:Leen TK:Muller KR, ed. pp.335

Sima J (1995) Hopfield languages Proc 22nd Seminar on Current Trends in Theory and Practice of Informatics 1012:461-468

Sima J (1997) Analog stable simulation of discrete neural networks Neural Network World 7:679-686

Sima J (2001) The computational capabilities of neural networks (extended abstract) Proc 5th Intl Conf Artif Neural Networks and Genetic Algorithms :22-26

Sima J, Orponen P (2000) A continuous-time Hopfield net simulation of discrete neural networks Proc 2nd Intl ICSC Symposium Neural Computation :36-42

Sima J, Orponen P (2001) Exponential transients in continuous-time symmetric Hopfield nets Proc 11th Intl Conf Artif Neural Networks 2130:806-813

Síma J, Orponen P (2003) Continuous-time symmetric Hopfield nets are computationally universal. Neural Comput 15:693-733 [Journal] [PubMed]

Sima J, Orponen P, Antti-Poika T (2000) On the computational complexity of binary and analog symmetric hopfield nets Neural Comput 12:2965-89 [PubMed]

Sima J, Wiedermann J (1998) Theory of neuromata J ACM 45:155-178

Siu KY, Bruck J, Kailath T, Hofmeister T (1993) Depth efficient neural networks for division and related problems IEEE Trans Inform Theory 39:946-956

Siu KY, Roychowdhury V, Kailath T (1995) Discrete neural computation; A theoretical foundation

Siu KY, Roychowdhury VP (1994) On optimal depth threshold circuits for multiplication and related problems SIAM J Discrete Math 7:284-292

Siu KY, Roychowdhury VP, Kailath T (1991) Depth-size tradeoffs for neural computation IEEE Trans Computers 40:1402-1412

Siu KY, Roychowdhury VP, Kailath T (1993) Computing with almost optimal size neural networks Advances In Neural Information Processing Systems, Hanson SJ:Cowan JD:Giles CL, ed. pp.19

Siu KY, Roychowdhury VP, Kailath T (1994) Rational approximation techniques for analysis of neural networks IEEE Trans Inform Theory 40:455-466

Siu KY, Roychowdhury VP, Kailath T (1995) Toward massively parallel design of multipliers J Parallel And Distributed Computing 24:86-93

Sorel M, Sima J (2000) Robust implementation of finite automata by recurrent RBF networks Proc 27th Seminar on Current Trends in Theory and Practice of Informatics 1963:431-439

Tanaka F, Edwards SF (1980) Analytic theory of the ground state properties of a spin glass: I. Ising spin glass J Phys F Metal Physics 10:2769-2778

Tchuente M (1986) Sequential simulation of parallel iterations and applications Theoretical Computer Science 48:135-144

Vollmer H (1999) Introduction to circuit complexity

von_Neumann J (1956) Automata Studies, Shannon CE:McCarthy J, ed. pp.43

Wegener I (1987) The complexity of Boolean functions

Wegener I (1993) Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions Inform Proc Lett 46:85-87

Werbos PJ (1974) Beyond regression: New tools for prediction and analysis in the behavioral sciences Unpublished doctoral dissertation

Wiedermann J (1994) Complexity issues in discrete neurocomputing Neural Network World 4:99-119

Yao ACC (1985) Separating the polynomial time hierarchy by oracles Proc 26th Annual Symposium on the Foundations of Computer Science :420-428

Yuille AL, Geiger D (2003) Winner-take-all networks The handbook of brain theory and neural networks (2nd ed), Arbib MA, ed. pp.1228