23 papers · ranked by Valyu relevance
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probability that a system will be in a certain state compared to the rest of the elements in the distribution. Because classical entropy-based Maxent…
Hector Zenil
Some established and also novel techniques in the field of applications of algorithmic (Kolmogorov) complexity currently co-exist for the first time and are here reviewed, ranging from dominant ones such as statistical lossless compression to newer approaches that advance, complement and also pose new challenges and…
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon’s entropy, lossless compressibility…
Hector Zenil, James A. R. Marshall, Jesper Tegnér
Being able to objectively characterize the intrinsic complexity of behavioral patterns resulting from human or animal decisions is fundamental for deconvolving cognition and designing autonomous artificial intelligence systems. Yet complexity is difficult in practice, particularly when strings are short. By numerically…
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
We introduce a definition of algorithmic symmetry in the context of geometric and spatial complexity able to capture mathematical aspects of different objects using as a case study polyominoes and polyhedral graphs. We review, study and apply a method for approximating the algorithmic complexity (also known as…
Kamaludin Dingle, Javor K. Novev, Sebastian E. Ahnert, Ard A. Louis
Unravelling the structure of genotype-phenotype (GP) maps is an important problem in biology. Recently, arguments inspired by algorithmic information theory (AIT) and Kolmogorov complexity have been invoked to uncover simplicity bias in GP maps, an exponentially decaying upper bound in phenotype probability with…
Hector Zenil, Santiago Hernández-Orozco, Narsis A. Kiani, Fernando Soler-Toscano + 2 more
'Fernando Soler-Toscano' 'Antonio Rueda-Toicen' 'Jesper Tegnér'] We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based on Solomonoff-Levin’s theory of algorithmic probability…
Gil Kalai
In this lecture I will talk about three mathematical puzzles involving mathematics and computation that have preoccupied me over the years. The first puzzle is to understand the amazing success of the simplex algorithm for linear programming. The second puzzle is about errors made when votes are counted during…
Alexander Ngu
This paper uses the concept of algorithmic efficiency to present a unified theory of intelligence. Intelligence is defined informally, formally, and computationally. We introduce the concept of Dimensional complexity in algorithmic efficiency and deduce that an optimally efficient algorithm has zero Time complexity…
Andrew N. Sloss
Algorithms are becoming more capable, and with that comes hic sunt dracones ("here be dragons"). The term symbolizes areas beyond our known maps. We use this term since we are stepping into an exciting, potentially dangerous, and unknown area with algorithms. Our curiosity to understand the natural world drives our…
John S. Nicolis
Finally, it gives a complete proof that a certain decision problem in NP has an algorithmic exponential lower bound thus establishing firmly that P≠NP. The proof presents a new way of approaching the subject: neither by entering into the unmanageable difficulties of proving this type of lower bound for the known…
Giulio Ruffini, David Ibañez, Eleni Kroupi, Jean-François Gagnon + 4 more
Idiopathic REM sleep behavior disorder (RBD) is a serious risk factor for neurodegenerative processes such as Parkinson’s disease (PD). We investigate the use of EEG algorithmic complexity derived metrics for its prognosis. We analyzed resting state EEG data collected from 114 idiopathic RBD patients and 83 healthy…
Hajo Broersma, Susan Stepney, Göran Wendin
For many decades, Moore's Law (Moore; 1965) gave us exponentially-increasing classical (digital) computing (CCOMP) power, with a doubling time of around 18 months. This cannot continue indefinitely, due to ultimate physical limits (Lloyd; 2000). Well before then, more practical limits will slow this increase. One such…
Feng Pan, Heng-Liang Zhang, Jie Qi
Computational complexity is a particularly important objective. The idea of Landauer principle was extended through mapping three classic problems (sorting、 ordered searching and max of N unordered numbers) into Maxwell demon thought experiment in this paper. The problems' complexity is defined on the entropy basis and…
Juan P. Franco, Karlo Doroc, Nitin Yadav, Peter Bossaerts + 1 more
The survival of human organisms depends on our ability to solve complex tasks in the face of limited cognitive resources. However, little is known about the factors that drive the complexity of those tasks. Here, building on insights from computational complexity theory, we quantify the computational hardness of…
TF Varley, A Luppi, I Pappas, L Naci + 4 more
The brain is possibly the most complex system known to mankind, and its complexity has been called upon to explain the emergence of consciousness. However, complexity can take many forms: here, we investigate measures of algorithmic and process complexity in both the temporal and topological dimension, testing them on…
Anurag Dutta, K. Lakshmanan, John Harshith, Aditya Ramamoorthy
—Time Complexity is an important metric to compare algorithms based on their cardinality. The commonly used, trivial notations to qualify the same are the Big-Oh, Big-Omega, Big-Theta, Small-Oh, and Small-Omega Notations. All of them, consider time a part of the real entity, i.e., Time coincides with the horizontal…
Juan Pablo Franco, Nitin Yadav, Peter Bossaerts, Carsten Murawski
Life presents us with decisions of varying degrees of difficulty. Many of them are NP-hard, that is, they are computationally intractable. Two important questions arise: which properties of decisions drive extreme computational hardness and what are the effects of these properties on human-decision making? Here, we…
Authors not listed
The Hidden Subgroup Problem (HSP) unifies several landmark quantum algorithms, yet systematic exploration of its variants and modern applications has slowed. This paper revives HSP-based algorithm design by examining new group structures with direct relevance to post-quantum cryptography, lattice problems, and…
Lionel Zoubritzky, François-Xavier Coudert
We present here an open-source Julia library for the topological identification of crystalline materials, with algorithmic and computational improvements over the previously available software in the field, resulting in a speed increase of one order of magnitude. This new algorithm and implementation can therefore be…
Authors not listed
We present a unified theoretical framework that classifies and analyzes quantum enhancement strategies for classical algorithms, establishing design paradigms that systematically combine quantum subroutines with classical procedures. The theory identifies four fundamental enhancement mechanisms: quantum search…
Authors not listed
Step-by-step thinking is essential in all domains of chemical sciences and engineering. While machine learning tools are broadly used, algorithms that automate reasoning are far less common. We elaborate on seven categories of human reasoning activities and connect each to applications in chemical science and…
Trevor Gokey, David L. Mobley
Molecular mechanics force fields require a chemical perception model to assign parameters to molecules. A recent advancement in force fields is the use of the SMARTS substructure query language as the perception model. Although it is straightforward to write SMARTS patterns to define new force field parameters, it is…