Wolfgang Merkle

  • Heidelberg University, Germany

According to our database1, Wolfgang Merkle authored at least 49 papers between 1997 and 2022.

Collaborative distances:



In proceedings 
PhD thesis 


Online presence:

On csauthors.net:


Normalized information distance and the oscillation hierarchy.
J. Comput. Syst. Sci., 2022

Searching for shortest and least programs.
Theor. Comput. Sci., 2020

Chaitin's ω as a continuous function.
J. Symb. Log., 2020

Speedable Left-c.e. Numbers.
Proceedings of the Computer Science - Theory and Applications, 2020

Being low along a sequence and elsewhere.
J. Symb. Log., 2019

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

Theory Comput. Syst., 2015

Solovay functions and their applications in algorithmic randomness.
J. Comput. Syst. Sci., 2015

Time-Bounded Kolmogorov Complexity and Solovay Functions.
Theory Comput. Syst., 2013

Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees.
Theory Comput. Syst., 2013

Analogues of Chaitin's Omega in the computably enumerable sets.
Inf. Process. Lett., 2013

Selection by Recursively Enumerable Sets.
Proceedings of the Theory and Applications of Models of Computation, 2013

Computability in Europe 2009.
Theory Comput. Syst., 2012

Separations of non-monotonic randomness notions.
J. Log. Comput., 2012

Constant Compression and Random Weights.
Comput., 2012

Solovay functions and K-triviality.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Traceable Sets.
Proceedings of the Theoretical Computer Science, 2010

Constructive equivalence relations on computable probability measures.
Ann. Pure Appl. Log., 2009

The complexity of stochastic sequences.
J. Comput. Syst. Sci., 2008

When unlearning helps.
Inf. Comput., 2008

A Simple Proof of Miller-Yu Theorem.
Fundam. Informaticae, 2008

Generation Complexity Versus Distinction Complexity.
Proceedings of the Theory and Applications of Models of Computation, 2008

Effective Randomness for Computable Probability Measures.
Electron. Notes Theor. Comput. Sci., 2007

Reconciling Data Compression and Kolmogorov Complexity.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

On C-Degrees, H-Degrees and T-Degrees.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

Selection Functions that Do Not Preserve Normality.
Theory Comput. Syst., 2006

Some Results on Effective Randomness.
Theory Comput. Syst., 2006

Schnorr dimension.
Math. Struct. Comput. Sci., 2006

Kolmogorov-Loveland randomness and stochasticity.
Ann. Pure Appl. Log., 2006

Generality's price: Inescapable deficiencies in machine-learned programs.
Ann. Pure Appl. Log., 2006

Kolmogorov Complexity and the Recursion Theorem.
Proceedings of the STACS 2006, 2006

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

On the construction of effectively random sets.
J. Symb. Log., 2004

Trees and learning.
J. Comput. Syst. Sci., 2004

Refuting learning revisited.
Theor. Comput. Sci., 2003

Almost complete sets.
Theor. Comput. Sci., 2003

The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences.
J. Symb. Log., 2003

Lattice Embeddings for Abstract Bounded Reducibilities.
SIAM J. Comput., 2002

On the Autoreducibility of Random Sequences
Electron. Colloquium Comput. Complex., 2002

On the Construction of Effective Random Sets.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Structural properties of bounded relations with an application to NP optimization problems.
Theor. Comput. Sci., 2001

Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities.
Math. Log. Q., 2001

Hausdorff Dimension in Exponential Time.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

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

Exact Pairs for Abstract Bounded Reducibilities.
Math. Log. Q., 1999

The Global Power of Additional Queries to p-random Oracles.
Electron. Colloquium Comput. Complex., 1999

A generalized account of resource bounded reducibilities.
PhD thesis, 1997

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