Commented bibliography:

iconnew indicates that the paper has been made available recently.
Click on  to download the online version of the paper.

Click on  for supporting material associated to the paper or the direct link to the journal.


Forthcoming book!
H. Zenil, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit, Methods and Applications of Algorithmic Complexity, Springer-Verlag, forthcoming in 2017.


Selected Papers:

  • iconnew H. Zenil and N.A. Kiani, Low Algorithmic Complexity Entropy-deceiving Graphs, arXiv:1608.05972, 2016. [preprint]
  • iconnew H. Zenil, F. Soler-Toscano, N.A. Kiani, S. Hernández-Orozco, A. Rueda-Toicen, A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity, arXiv:1609.00110, 2016. [preprint]
  • iconnew H. Zenil, N.A. Kiani and J. Tegnér, Methods of Information Theory and Algorithmic Complexity for Network Biology, Seminars in Cell and Developmental Biology vol. 51, pp. 32-43, 2016. doi:10.1016/j.semcdb.2016.01.011 [onlinepreprint]
  • Algorithmic complexity for psychology: A user-friendly implementation of the coding theorem method
    N. Gauvrit,  H. Singmann, F. Soler-Toscano, H. Zenil*
    Behavior Research Methods, Volume 48, Issue 1, pp. 1-16, 2015. DOI: 10.3758/s13428-015-0574-3 [preprintonline]
  • N. Gauvrit, F. Soler-Toscano, H. Zenil, Natural scene statistics mediate the perception of image complexity, Visual Cognition, 2014. electronic version ahead of press DOI: 10.1080/13506285.2014.950365 (a strong result on the correlation of natural scene statistics, complexity and human subjective randomness)
  • V. Kempe, N. Gauvrit, D. Forsyth, Structure emerges faster during cultural transmission in children than in adults, vol 136, pp 247–254, Cognition, 2015.
  • H. Zenil, F. Soler-Toscano, K. Dingle and A. Louis, Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks, Physica A: Statistical Mechanics and its Applications, vol. 404, pp. 341–358, 2014. . (an application of Kolmogorov complexity to graph theory and complex networks)
  • F. Soler-Toscano, H. Zenil, J-P. Delahaye and Nicolas Gauvrit, Calculating Kolmogorov Complexity from the Frequency Output Distributions of Small Turing MachinesPLoS ONE 9(5): e96223, 2014. (taking the technique alternative to compression algorithms to its limits, deals with the complexity of short strings)
  • N. Gauvrit, K. Morsanyi, The Equiprobability Bias from a Mathematical and Psychological Perspective, Advances in Cognitive Psycology, pp. 119-130, 2014. DOI:10.5709/acp-0163-9.
  • J.-L. Dessalles, Algorithmic simplicity and relevance, Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence, Lecture Notes in Computer Science Volume 7070, pp 119-130, 2013.
  • N. Gauvrit, H. Zenil, F. Soler-Toscano and J.-P. Delahaye, Algorithmic complexity for short binary strings applied to psychology: a primer, Behavior Research Methods, 2014 Sep;46(3):732-44. doi: 10.3758/s13428-013-0416-0.
  • H. Zenil, F. Soler-Toscano, J-P. Delahaye and Nicolas Gauvrit, Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility,PeerJ Computer Science, 1:e23, 2015 [online]. (exploring a 2-dimensional universal distribution with 2-dimensional Turing machines, and providing further evidence that the method is sound by comparing it to compression results)
  •  F. Soler-Toscano, H. Zenil, J-P. Delahaye and Nicolas Gauvrit, Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures, Computability, vol. 2, no. 2, pp 125-140, 2013. DOI 10.3233/COM-13019 (justifying the method in terms of program-size and comparison to other complexity measures notably Bennett’s logical depth)
  • J-P. Delahaye and H. Zenil, Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness, Applied Mathematics and Computation, 219, pp. 63-77, 2012. DOI:10.1016/j.amc.2011.10.006(the first important step towards the complexity calculator and the full deployment of the novel technique)
  • J.J. Joosten, F. Soler-Toscano and H. Zenil, Program-size versus Time Complexity. Slowdown and Speed-up Phenomena in the Micro-cosmos of Small Turing Machines, International Journal of Unconventional Computing, Special issue on Physics & Computation 2011. (first experimental paper on the tradeoffs between time complexity and program-size (Kolmogorov) complexity)
  •  H. Zenil, Turing Patterns with Turing Machines: Emergence and Low-level Structure Formation, Natural Computing (formal connections between structure and patterns in nature),  DOI: 10.1007/s11047-013-9363-z, 2013.
  • J. J. Joosten, On the necessity of complexity. In H. Zenil (ed), Irreducibility and Computational Equivalence: 10 Years After the Publication of Wolfram’s A New Kind of Science, Springer Verlag, 2013. Book webpage.
  • J. J. Joosten, Complexity fits the fittest. In I. Zelinka, A. Sanayei, H. Zenil, O. E. Rossler (eds), Emergence, Complexity and Computation in Nature, Springer Verlag, to appear in 2013.
  • H. Zenil, From Computer Runtimes to the Length of Proofs: With an Algorithmic Probabilistic Application to Waiting Times in Automatic Theorem Proving. In M.J. Dinneen, B. Khousainov, and A. Nies (Eds.), Computation, Physics and Beyond, Theoretical Computer Science and Applications, WTCS 2012 (Calude’s Festschrift), LNCS 7160, pp. 223-240, Springer, 2012. DOI:10.1007/978-3-642-27654-5_17
  • H. Zenil, F. Soler-Toscano and J.J. Joosten, Empirical Encounters with Computational Irreducibility and Unpredictability, Minds and Machines, vol. 22, Number 3, pp. 149-165, 2012. DOI: 10.1007/s11023-011-9262-y

  • H. Zenil, J.P. Delahaye and C. Gaucherel, Image Characterization and Classification by Physical ComplexityComplexity, vol. 17–3, pages 26-42, 2012. (online 2011) DOI:10.1002/cplx.20388(first ever application motivated by Bennett’s logical depth)
  • H. Zenil and J-P. Delahaye, On the algorithmic nature of the world, in M. Burgin, G. Dodig-Crnkovic (eds), Information and Computation, World Scientific, 2010. (philosophical implications and reflections)
  • H. Zenil, Compression-based investigation of the dynamical properties of cellular automata and other systems, Complex Systems, 14:2, 2010. (towards making a connection to the compression-technique)
  • H. Zenil and J.P. Delahaye, An algorithmic information-theoretic approach to the behaviour of financial markets, themed issue on Nonlinearity, Complexity and Randomness, Journal of Economic Surveys, 2011. (first application)
  • H. Zenil, The World is Either Algorithmic or Mostly Random, FXQi Contest: Is Reality Digital or Analog?, 3rd Prize winner, February 2011. (some philosophical interpretations of our work, has attracted some financial support to the group)

  • J-P. Delahaye and H. Zenil, Towards a stable definition of Kolmogorov-Chaitin complexity, in preparation. (first draft available).
  • J-P. Delahaye and H. Zenil, On the Kolmogorov-Chaitin complexity for short sequences, in Randomness and Complexity: From Leibniz to Chaitin. In C.S. Calude (ed), World Scientific, 2007. (the founding article)

In other languages (French and Spanish):

  • iconnew The Spanish edition of Scientific American (Investigación y Ciencia) No. 447 publishes an article entitled “From Digital Universes to the MindNew tools to quantify our intuition of complexity and randomness” (De los universos digitales a la mente: Nuevas herramientas para cuantificar nuestra intuición sobre la complejidad y el azar).  Full article here.
  • iconnewThe French edition of Scientific American (Pour La Science) No. 405 devoted the Logic and Computation (Logique et Calcul) section of its July 2011 issue to our work on Kolmogorov complexity for short strings under the title “Le défi des faibles complexités” (The challenge of weak complexities). Full article here. (the popularisation article)
  • H. Zenil, and J.-P. Delahaye, Un método estable para la evaluación de la complejidad algorítmica de cadenas cortas (A Stable Method for the Evaluation of the Algorithmic Complexity of Short Strings). In G.J. Martinez, H. Zenil and C.R. Stevens (eds), Complex Systems as Computing Models, Luniver Press, 2011.
  • J.J. Joosten, F. Soler-Toscano, H. Zenil, Complejidad descriptiva y computacional en máquinas de Turing pequeñas, En Lógica Universal e Unidade da Ciência, Centro de Filosofia das Ciências da Universidade de Lisboa, pp. 11–32, 2011.
  • H. Zenil, El Universo Algorítmico. In, O. Miramontes and K. Volke (eds.) Fronteras de la Física en el Siglo XXI, CopIt arXives, UNAM, (forthcoming)
  • H. Zenil, De formas y bits: Emergencia de patrones y estructura en la naturaleza, Ciencia, revista de la Academia Mexicana de Ciencias, número especial dedicado a Alan Turing, 2013-1.  (forthcoming)

In proceedings:

  • J.J. Joosten, F. Soler-Toscano and H. Zenil, Program-size versus Time complexity, Slowdown and speed-up phenomena in the micro-cosmos of small Turing machines In H. Guerra (ed.). Physics and Computation 2010, Pre-Proceedings, CAMIT, University of Azores, 3rd International Workshop on Physics and Computation, Luxor, Egypt, 2010.
  • J.J. Joosten, H. Zenil and F. Soler-Toscano, Fractal Dimension as an Indication of the Terminating Runtime of Discrete Dynamical Systems, (abstract p. 214) in S. Thurner M. Szell (eds), Löcker Verlag, ECCS’11, Vienna 2011.


Relevant books by the group members:

H. Zenil (ed), Randomness Through Computation: Some Answers, More Questions, World Scientific, Singapore, 2011.

N. Gauvrit and J.-P. Delahaye, Comme par hasard ! : Coïncidences et loi des séries,, France, 2012.

J.-P. DelahayeComplexité aléatoire et complexité organisée, Editions Quae, France, 2009.

N. Gauvrit, Vous avez dit hasard ? : Entre psychologie et mathématiques, Belin, France, 2009.

J.-P. DelahayeComplexités : Aux limites des mathématiques et de l’informatique, Pour La Science, Bibliothèque Scientifique, France, 2006.

F. Soler-Toscano, Razonamiento abductivo en lógica clásica, College Publications, UK, 2012.


The group has published so far in the following journals:

PLoS ONE, Physica A, Visual Cognition, Computability, Natural Computing, Applied Mathematics and Computation, Cognition, Complexity, Behavior Research Methods, Minds and Machines, Complex Systems, International Journal of Unconventional Computing and Advances in Cognitive Psycology. There is also a book forthcoming from Springer Verlag.