Wolfgang Merkle

Inf. Comput., 2025

2024

Randomness Versus Superspeedability.

[BibT_eX]

[DOI]

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023

Relativized depth.

[BibT_eX]

[DOI]

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

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

Constant compression and random weights.

[BibT_eX]

[DOI]

Jason Teutsch

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 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

Time-Bounded Kolmogorov Complexity and Solovay Functions.

[BibT_eX]

[DOI]

Rupert Hölzl

Thorsten Kräling

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Separations of Non-monotonic Randomness Notions.

[BibT_eX]

[DOI]

Proceedings of the Sixth International Conference on Computability and Complexity in Analysis, 2009

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

Effective Randomness for Computable Probability Measures.

[BibT_eX]

[DOI]

Proceedings of the Third International Conference on Computability and Complexity in Analysis, 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

2005

Kolmogorov-Loveland Randomness and Stochasticity.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

Schnorr Dimension.

[BibT_eX]

[DOI]

Rodney G. Downey

Jan Reimann

Proceedings of the New Computational Paradigms, 2005

2004

On the construction of effectively random sets.

[BibT_eX]

[DOI]

Nenad Mihailovic

J. Symb. Log., 2004

Some Results on Effective Randomness.

[BibT_eX]

[DOI]

Nenad Mihailovic

Theodore A. Slaman

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

On Selection Functions that Do Not Preserve Normality.

[BibT_eX]

[DOI]

Jan Reimann

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Generality's Price: Inescapable Deficiencies in Machine-Learned Programs.

[BibT_eX]

[DOI]

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

The complexity of stochastic sequences.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Lattice Embeddings for Abstract Bounded Reducibilities.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

On the Autoreducibility of Random Sequences

[BibT_eX]

[DOI]

Todd Ebert

Heribert Vollmer

Electron. Colloquium Comput. Complex., 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

The Kolmogorov-Loveland Stochastic Sequences Are Not Closed under Selecting Subsequences.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Hausdorff Dimension in Exponential Time.

[BibT_eX]

[DOI]

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

Refuting Learning Revisited.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 12th International Conference, 2001

2000

Almost Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

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

[BibT_eX]

[DOI]

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

Unlearning Helps.

[BibT_eX]

[DOI]

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

1997

A generalized account of resource bounded reducibilities.

[BibT_eX]

[DOI]

PhD thesis, 1997

Proving the PCP-Theorem.

[BibT_eX]

[DOI]

Volker Heun

Ulrich Weigand

Proceedings of the Lectures on Proof Verification and Approximation Algorithms. (the book grow out of a Dagstuhl Seminar, 1997

1996

Exact Pairs for Abstract Bounded Reducibilities.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 10th International Workshop, 1996

Trees and Learning.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996

1995

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

[BibT_eX]

[DOI]