The Nature of Computation

By Cristopher Moore, S. Mertens. 2011

422 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/0d596d9de8068c1f98424e826e4be59fecd87c0f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

Inverse statistical problems: from the inverse Ising problem to data science (2017, neutral): “[136]).”
Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes (2016, background): “…properties of a stochastic process in terms of a probability distribution over the configurations σ of the system P (σ;β) = Z (β)−1 exp (−βE (σ)), where E (σ) is the energy of the configuration, β an inverse temperature, and the normalization factor Z (β) is called the partition function and…”
Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses. (2015, background): “…e.g. Monte Carlo algorithms [13,14] (a situation typical of spin glass phases, which is common to many hard random optimization problems [15 – 17]); moreover, the optimal synaptic configurations are typically geometrically isolated (i.e., they have mutual Hamming distances of order N ), and…”
Cognitive computational neuroscience (2018, background): “The formalism of production systems also provides a universal computational architecture.(133) Production systems such as ACT-R 5 were originally developed under the guidance of behavioral data.”
Quantum computation vs. firewalls (2013, background): “For a discussion of the vast support for this conjecture, see for example [57].”
Statistical physics of inference: thresholds and algorithms (2015, background): “This is in fact a crucial property in the demonstrations of many results in the physics of disordered systems, and in computer science this is the inequality behind the “first moment method” [173].”
Complexity and entanglement for thermofield double states (2018, methodology): “hole interior. It has been suggested that this quantity is the quantum computational complexity of the boundary state [10]. The concept of circuit complexity is rooted in theoretical computer science [15,16]. In classical computing, one is interested in implementing a given algorithm, i.e., a functi”
Circuit complexity for free fermions (2018, background): “, and we also consider the complexity of various excited states. 2 Complexity, Nielsen and group theory The concept of complexity stems from the notion of computational complexity in computer science [45,46]. The question of interest is to ask how much of certain computational resources are required”
Sampling of partially distinguishable bosons and the relation to the multidimensional permanent (2014, background): “Few physical problems ﬁt in the categories of computational complexity theory [1].”