This thesis examines so called folding neural networks as a mechanism for machine learning. Folding networks form a generalization of partial recurrent neural networks such that they are able to deal with tree structured inputs instead of simple linear lists. In particular, they can handle classical formulas - they were proposed originally for this purpose. After a short explanation of the neural architecture we show that folding networks are well suited as a learning mechanism in principle. This includes three parts: the proof of their universal approximation ability, the aspect of information theoretical learnability, and the examination of the complexity of training. Approximation ability: It is shown that any measurable function can be approximated in probability. Explicit bounds on the number of neurons result if only a finite number of points is dealt with. These bounds are new results in the case of simple recurrent networks, too. Several restrictions occur if a function is to be approximated in the maximum norm. Afterwards, we consider briefly the topic of computability. It is shown that a sigmoidal recurrent neural network can compute any mapping in exponential time. However, if the computation is subject to noise almost the capability of tree automata arises. Information theoretical learnability: This part contains several contributions to distribution dependent learnability: The notation of PAC and PUAC learnability, consistent PAC/ PUAC learnability, and scale sensitive versions are considered. We find equivalent characterizations of these terms and examine their respective relation answering in particular an open question posed by Vidyasagar. It is shown at which level learnability only because of an encoding trick is possible. Two approaches from the literature which can guarantee distribution dependent learnability if the VC dimension of the concept class is infinite are generalized to function classes: The function class is stratified according to the input space or according to a so-called luckiness function which depends on the output of the learning algorithm and the concrete training data. Afterwards, the VC, pseudo-, and fat shattering dimension of folding networks are estimated: We improve some lower bounds for recurrent networks and derive new lower bounds for the pseudodimension and lower and upper bounds for folding networks in general. As a consequence, folding architectures are not distribution independent learnable. Distribution dependent learnability can be guaranteed. Explicit bounds on the number of examples which guarantee valid generalization can be derived using the two approaches mentioned above. We examine in which cases these bounds are polynomial. Furthermore, we construct an explicit example for a learning scenario where an exponential number of examples is necessary. Complexity: It is shown that training a fixed folding architecture with perceptron activation function is polynomial. Afterwards, a decision problem, the so-called loading problem, which is correlated to neural network training is examined. For standard multilayer feed-forward networks the following situations turn out to be NP-hard: Concerning the perceptron activation function, a classical result from the literature, the NP-hardness for varying input dimension, is generalized to arbitrary multilayer architectures. Additionally, NP-hardness can be found if the input dimension is fixed but the number of neurons may vary in at least two hidden layers. Furthermore, the NP-hardness is examined if the number of patterns and number of hidden neurons are correlated. We finish with a generalization of the classical NP result as mentioned above to the sigmoidal activation function which is used in practical applications.

Adaptability and flexibility are some of the most important human characteristics. Learning based on new experiences enables adaptation by changing the structural connectivity of the brain through plasticity mechanisms. But the human brain can also adapt to new tasks and situations in a matter of milliseconds by dynamic coordination of functional activation. To understand how this flexibility can be achieved in the computations performed by neural networks, we have to understand how the relatively fixed structural backbone interacts with the functional dynamics. In this thesis, I will analyze these interactions between the structural network connectivity and functional activations and their dynamic interactions on different levels of abstraction and spatial and temporal scales. One of the big questions in neuroscience is how functional interactions in the brain can adapt instantly to different tasks while the brain structure remains almost static. To improve our knowledge of the neural mechanisms involved, I will first analyze how dynamics in functional brain activations can be simulated based on the structural brain connectivity obtained with diffusion tensor imaging. In particular, I will show that a dynamic model of functional connectivity in the human cortex is more predictive of empirically measured functional connectivity than a stationary model of functional dynamics. More specifically, the simulations of a coupled oscillator model predict 54\% of the variance in the empirically measured EEG functional connectivity. Hypotheses of temporal coding have been proposed for the computational role of these dynamic oscillatory interactions on fast timescales. These oscillatory interactions play a role in the dynamic coordination between brain areas as well as between cortical columns or individual cells. Here I will extend neural network models, which learn unsupervised from statistics of natural stimuli, with phase variables that allow temporal coding in distributed representations. The analysis shows that synchronization of these phase variables provides a useful mechanism for binding of activated neurons, contextual coding, and figure ground segregation. Importantly, these results could also provide new insights for improvements of deep learning methods for machine learning tasks. The dynamic coordination in neural networks has also large influences on behavior and cognition. In a behavioral experiment, we analyzed multisensory integration between a native and an augmented sense. The participants were blindfolded and had to estimate their rotation angle based on their native vestibular input and the augmented information. Our results show that subjects alternate in the use between these modalities, indicating that subjects dynamically coordinate the information transfer of the involved brain regions. Dynamic coordination is also highly relevant for the consolidation and retrieval of associative memories. In this regard, I investigated the beneficial effects of sleep for memory consolidation in an electroencephalography (EEG) study. Importantly, the results demonstrate that sleep leads to reduced event-related theta and gamma power in the cortical EEG during the retrieval of associative memories, which could indicate the consolidation of information from hippocampal to neocortical networks. This highlights that cognitive flexibility comprises both dynamic organization on fast timescales and structural changes on slow timescales. Overall, the computational and empirical experiments demonstrate how the brain evolved to a system that can flexibly adapt to any situation in a matter of milliseconds. This flexibility in information processing is enabled by an effective interplay between the structure of the neural network, the functional activations, and the dynamic interactions on fast time scales.