Wolfgang Merkle

Valentino Delle Rose

Theor. Comput. Sci., March, 2023

2022

Normalized information distance and the oscillation hierarchy.

[BibT_eX]

[DOI]

Klaus Ambos-Spies

Sebastiaan A. Terwijn

J. Comput. Syst. Sci., 2022

2020

Searching for shortest and least programs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Chaitin's ω as a continuous function.

[BibT_eX]

[DOI]

J. Symb. Log., 2020

Speedable Left-c.e. Numbers.

[BibT_eX]

[DOI]

Ivan Titov

Proceedings of the Computer Science - Theory and Applications, 2020

2019

Being low along a sequence and elsewhere.

[BibT_eX]

[DOI]

Liang Yu

J. Symb. Log., 2019

2017

Guest Editorial: Tenth International Conference on Computability, Complexity and Randomness (CCR 2015).

[BibT_eX]

[DOI]

Andrew Lewis-Pye

Theory Comput. Syst., 2017

2015

Editorial.

[BibT_eX]

[DOI]

Elvira Mayordomo

Theory Comput. Syst., 2015

Solovay functions and their applications in algorithmic randomness.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

2013

Time-Bounded Kolmogorov Complexity and Solovay Functions.

[BibT_eX]

[DOI]

Rupert Hölzl

Thorsten Kräling

Theory Comput. Syst., 2013

Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

Analogues of Chaitin's Omega in the computably enumerable sets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

Selection by Recursively Enumerable Sets.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2013

2012

Computability in Europe 2009.

[BibT_eX]

[DOI]

Arnold Beckmann

Benedikt Löwe

Theory Comput. Syst., 2012

Separations of non-monotonic randomness notions.

[BibT_eX]

[DOI]

J. Log. Comput., 2012

Constant Compression and Random Weights.

[BibT_eX]

[DOI]

Jason Teutsch

Comput., 2012

2011

Solovay functions and K-triviality.

[BibT_eX]

[DOI]

André Nies

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010

Traceable Sets.

[BibT_eX]

[DOI]

Rupert Hölzl

Proceedings of the Theoretical Computer Science, 2010

2009

Constructive equivalence relations on computable probability measures.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2009

2008

The complexity of stochastic sequences.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

When unlearning helps.

[BibT_eX]

[DOI]

Inf. Comput., 2008

A Simple Proof of Miller-Yu Theorem.

[BibT_eX]

[DOI]

Alexander Shen

Fundam. Informaticae, 2008

Generation Complexity Versus Distinction Complexity.

[BibT_eX]

[DOI]

Rupert Hölzl

Proceedings of the Theory and Applications of Models of Computation, 2008

2007

Reconciling Data Compression and Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

On C-Degrees, H-Degrees and T-Degrees.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Selection Functions that Do Not Preserve Normality.

[BibT_eX]

[DOI]

Jan Reimann

Theory Comput. Syst., 2006

Some Results on Effective Randomness.

[BibT_eX]

[DOI]

Nenad Mihailovic

Theodore A. Slaman

Theory Comput. Syst., 2006

Schnorr dimension.

[BibT_eX]

[DOI]

Rodney G. Downey

Jan Reimann

Math. Struct. Comput. Sci., 2006

Effective Randomness for Computable Probability Measures.

[BibT_eX]

[DOI]

Proceedings of the Third International Conference on Computability and Complexity in Analysis, 2006

Kolmogorov-Loveland randomness and stochasticity.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2006

Generality's price: Inescapable deficiencies in machine-learned programs.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2006

Kolmogorov Complexity and the Recursion Theorem.

[BibT_eX]

[DOI]

Bjørn Kjos-Hanssen

Proceedings of the STACS 2006, 2006

06051 Abstracts Collection -- Kolmogorov Complexity and Applications.

[BibT_eX]

[DOI]

Marcus Hutter

Paul M. B. Vitányi

Proceedings of the Kolmogorov Complexity and Applications, 29.01. - 03.02.2006, 2006

2004

On the construction of effectively random sets.

[BibT_eX]

[DOI]

Nenad Mihailovic

J. Symb. Log., 2004

Trees and learning.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

2003

Refuting learning revisited.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Almost complete sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

On the Autoreducibility of Random Sequences.

[BibT_eX]

[DOI]

Todd Ebert

Heribert Vollmer

SIAM J. Comput., 2003

The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences.

[BibT_eX]

[DOI]

J. Symb. Log., 2003

2002

Lattice Embeddings for Abstract Bounded Reducibilities.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

On the Construction of Effective Random Sets.

[BibT_eX]

[DOI]

Nenad Mihailovic

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits.

[BibT_eX]

[DOI]

Todd Ebert

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001

Structural properties of bounded relations with an application to NP optimization problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

The Global Power of Additional Queries to P-Random Oracles.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities.

[BibT_eX]

[DOI]

Yongge Wang

Math. Log. Q., 2001

Hausdorff Dimension in Exponential Time.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Unlearning Helps.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Exact Pairs for Abstract Bounded Reducibilities.

[BibT_eX]

[DOI]

Math. Log. Q., 1999

1997

A generalized account of resource bounded reducibilities.

[BibT_eX]

[DOI]

PhD thesis, 1997

Proving the PCP-Theorem.

[BibT_eX]

[DOI]

Volker Heun