Citation Relationships

Legends: Link to a Model Reference cited by multiple papers


Síma J, Orponen P (2003) General-purpose computation with neural networks: a survey of complexity theoretic results. Neural Comput 15:2727-78 [PubMed]

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
(156 refs)