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 |