General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
From MaRDI portal
Publication:4819851
DOI10.1162/089976603322518731zbMath1097.68589OpenAlexW2148888011WikidataQ35589642 ScholiaQ35589642MaRDI QIDQ4819851
Publication date: 5 October 2004
Published in: Neural Computation (Search for Journal in Brave)
Full work available at URL: https://aaltodoc.aalto.fi/handle/123456789/30763
Related Items
Size and Energy of Threshold Circuits Computing Mod Functions ⋮ Complexity of reachability problems for finite discrete dynamical systems ⋮ \(Awaking\) and \(sleeping\) of a complex network ⋮ Convergence and stability of the split-step \(\theta\)-Milstein method for stochastic delay Hopfield neural networks ⋮ An RNA-based theory of natural universal computation ⋮ Subrecursive neural networks ⋮ Three analog neurons are Turing universal ⋮ Energy and depth of threshold circuits ⋮ Size-energy tradeoffs for unate circuits computing symmetric Boolean functions ⋮ Quasi-periodic \(\beta\)-expansions and cut languages ⋮ Rational analysis, intractability, and the prospects of `as if'-explanations ⋮ Computational capabilities of analog and evolving neural networks over infinite input streams ⋮ An object-oriented environment for developing finite element codes for multi-disciplinary applications ⋮ Energy Complexity of Recurrent Neural Networks ⋮ Positive Neural Networks in Discrete Time Implement Monotone-Regular Behaviors ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ Analog neuron hierarchy ⋮ Computing with Spikes: The Advantage of Fine-Grained Timing ⋮ A computational study of \(f\)-reversible processes on graphs ⋮ Reversible iterative graph processes ⋮ Cut Languages in Rational Bases ⋮ Rule Extraction from Recurrent Neural Networks: ATaxonomy and Review ⋮ Sequential Triangle Strip Generator Based on Hopfield Networks ⋮ Expressive power of first-order recurrent neural networks determined by their attractor dynamics ⋮ Neural networks for variational problems in engineering ⋮ ENERGY-EFFICIENT THRESHOLD CIRCUITS COMPUTING MOD FUNCTIONS ⋮ A Survey on Analog Models of Computation
Cites Work
- Dynamics of positive automata networks
- Decreasing energy functions as a tool for studying threshold networks
- On the construction of parallel computers from various basis of Boolean functions
- Asynchronous threshold networks
- Sequential simulation of parallel iterations and applications
- How easy is local search?
- Stability and looping in connectionist models with asymmetric weights
- Comportement périodique des fonctions à seuil binaires et applications
- Some notes on threshold circuits, and multiplication in depth 4
- Majority gates vs. general weighted threshold gates
- Information and self organization. A macroscopic approach to complex systems
- Computing with truly asynchronous threshold logic networks
- The structure of logarithmic advice complexity classes
- On computation with pulses
- On computing Boolean functions by a spiking neuron
- Approximability of the ground state problem for certain Ising spin glasses
- Analog computation via neural networks
- A family of universal recurrent networks
- Stochastic analog networks and computational complexity
- A theory of complexity for continuous time systems
- Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
- Transient length in sequential iteration of threshold functions
- On the complexity of learning for spiking neurons with temporal coding.
- On the computational power of neural nets
- On the geometric separability of Boolean functions
- The dynamic universality of sigmoidal neural networks
- On periodical behaviour in societies with symmetric influences
- Threshold circuits of bounded depth
- Theory of majority decision elements
- Hyperplane cuts of an n-cube
- Fast Sigmoidal Networks via Spiking Neurons
- Bounds for the number of threshold functions
- Simple Local Search Problems that are Hard to Solve
- Absolute stability of global pattern formation and parallel memory storage by competitive neural networks
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- The capacity of the Hopfield associative memory
- A generalized convergence theorem for neural networks
- Theory of neuromata
- The convergence of symmetric threshold automata
- On Threshold Circuits and Polynomial Computation
- Derandomizing Approximation Algorithms Based on Semidefinite Programming
- Depth efficient neural networks for division and related problems
- Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
- On Optimal Depth Threshold Circuits for Multiplication and Related Problems
- Efficient simulation of finite automata by neural nets
- On the Size of Weights for Threshold Gates
- Rational approximation techniques for analysis of neural networks
- Bounds for the Computational Power and Learning Complexity of Analog Neural Nets
- Computational power of neural networks: a characterization in terms of Kolmogorov complexity
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Simulating Threshold Circuits by Majority Circuits
- Networks of spiking neurons can emulate arbitrary Hopfield nets in temporal coding
- A Step towards a Complexity Theory for Analog Systems
- Descartes' Rule of Signs for Radial Basis Function Neural Networks
- On the Probability That a Random ± 1-Matrix Is Singular
- Lower Bounds for the Computational Power of Networks of Spiking Neurons
- Neural networks and physical systems with emergent collective computational abilities.
- Learning representations by back-propagating errors
- Neurons with graded response have collective computational properties like those of two-state neurons.
- Enumeration of Seven-Argument Threshold Functions
- Probabilistic automata
- Computational Work and Time on Finite Machines