Algorithmic Randomness and Complexity

By R. Downey, D. Hirschfeldt. Theory and Applications of Computability, 2010

961 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/b5e2697808c5890bcaeefa0afc05b90c51b8635c

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

The Deluge of Spurious Correlations in Big Data (2016, methodology): “…string in Van der Waerden theorem or a set in Ramsey theorem, our analysis will be based on algorithmic information theory, a mathematical theory studying (algorithmic) randomness for individual objects, in particular, strings and (ﬁnite) sets of numbers (Calude 2002; Downey and Hirschfeldt 2010).”
Medvedev degrees of two-dimensional subshifts of finite type (2012, neutral): “Two recent references are [15, 30].”
On uniform relationships between combinatorial problems (2012, result): “Theorem 5.28 (Hirschfeldt and Jockusch [18]) .”
On initial segment complexity and degrees of randomness (2008, background): “Many of our results will be stated in terms of the K-degrees, which were introduced by Downey, Hirschfeldt and LaForte [6, 7].”
Measures and Their Random Reals (2008, background): “It was independently obtained by Downey, Hirschfeldt, Miller, and Nies [2].”
Extracting information is hard: A Turing degree of non-integral effective Hausdorff dimension (2011, positive): “Algorithmic randomness. An introduction to algorithmic randomness can be found in the upcoming monographs of Downey and Hirschfeldt [ 4 ] and Nies [19] or the excellent survey paper of Downey, Hirschfeldt, Nies and Terwijn [6].”
Asymptotic Convergence in Online Learning with Unbounded Delays (2016, methodology): “In their canonical text, Downey and Hirschfeldt [3] give three diﬀerent deﬁnitions of algorithmic randomness and show them all to be equivalent.”