Wolfgang Merkle - Publications

Research articles

• Constant compression and random weights
  (with Jason Teutsch).
  
  Symposium on Theoretical Aspects of Computer Science 2012 (STACS 2012), to appear.
  

  ---

• Separations of non-monotonic randomness notions [PDF]
  (with Laurent Bienvenu, Rupert Hölzl, and Thorsten Kräling).
  
  Journal of Logic and Computation, to appear.
  Preliminary version in Conference on Computability and Complexity in Analysis 2009, Dagstuhl Research Online Publication Server DROPS.
  

  ---

• Solovay functions and K-triviality
  (with Laurent Bienvenu and André Nies).
  
  Symposium on Theoretical Aspects of Computer Science 2011 (STACS 2011), Leibniz International Proceedings in Informatics 9:452-463, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2011.
  

  ---

• Kolmogorov complexity and the recursion theorem [PDF]
  (with Bjørn Kjos-Hanssen and Frank Stephan).
  
  Transactions of the AMS 363:5465-5480, 2011.
  Preliminary version in Symposium on Theoretical Aspects of Computer Science 2006, LNCS 3884:149-161, Springer, 2006 [PDF].
  

  ---

• Traceable sets
  (with Rupert Hölzl).
  
  Theoretical Computer Science 2010 (IFIP TCS 2010), IFIP 323:301-315, Springer 2010.
  

  ---

• Constructive equivalence relations on computable probability measures [PDF]
  (with Laurent Bienvenu).
  
  Annals of Pure and Applied Logic 160:238-254, 2009.
  Preliminary version in Conference on Computability and Complexity in Analysis 2006, ENTCS 167:117-130, 2007.
  

  ---

• Time-bounded Kolmogorov complexity and Solovay functions [PDF]
  (with Rupert Hölzl and Thorsten Kräling).
  
  Mathematical Foundations of Computer Science 2009, LNCS 5734:392-402, Springer 2009.
  

  ---

• Generation complexity versus distinction complexity [PDF]
  (with Rupert Hölzl).
  
  Theory and Applications of Models of Computation 2008, LNCS 4978:457-466, Springer, 2008.

  ---

• Unlearning helps
  (with Ganesh Baliga, John Case, and Frank Stephan).
  
  Information and Computation 206:694-709, 2008.
  Preliminary version in International Colloquium on Automata, Languages and Programming 2000, LNCS 1853:844-855, Springer, 2000.

  ---

• The complexity of stochastic sequences. [PDF]
  
  Journal of Computer and System Sciences 74:350-357, 2008.
  Preliminary version in Conference on Computational Complexity 2003, p. 230-235, IEEE Computer Society Press, 2003.
  

  ---

• A simple proof of Miller-Yu Theorem [PDF]
  (with Laurent Bienvenu and Alexander Shen).
  
  Fundamenta Informaticae 83:1-4, 2008.
  

  ---

• Reconciling data compression and Kolmogorov complexity [PDF]
  (with Laurent Bienvenu).
  
  International Colloquium on Automata, Languages and Programming 2007, LNCS 4596:643-654, Springer 2007.
  

  ---

• On C-degrees, H-degrees, and T-degrees
  (with Frank Stephan).
  
  Conference on Computational Complexity 2007, p. 60-69, IEEE Computer Society Press, 2007.
  

  ---

• Kolmogorov-Loveland randomness and stochasticity [PS] [PDF]
  (with Joseph Miller, André Nies, Frank Stephan, and Jan Reimann).
  
  Annals of Pure and Applied Logic 138:183-210, 2006.
  Preliminary version in Symposium on Theoretical Aspects of Computer Science 2005, LNCS 3404:422-433, Springer, 2005.
  

  ---

• Generality's price: inescapable deficiencies in machine-learned programs [PS] [PDF]
  (with John Case, Keh-Jiann Chen, Sanjay Jain, and James S. Royer).
  
  Annals of Pure and Applied Logic 139:303-326, 2006.
  Preliminary version in Conference on Learning Theory 2003 (COLT 2003), LNCS 2777:684-698, Springer, 2003.

  ---

• Some results on effective randomness [PS]
  (with Nenad Mihailovic and Theodore A. Slaman).
  
  Theory of Computing Systems 39:707-721, 2006.
  Preliminary version in International Colloquium on Automata, Languages and Programming 2004, LNCS 3142:983-995, Springer, 2004.

  ---

• On selection functions that do not preserve normality [PS]
  (with Jan Reimann).
  
  Theory of Computing Systems 39:685-697, 2006.
  Preliminary version in Mathematical Foundations of Computer Science 2003, LNCS 2747:602-611, Springer, 2003.

  ---

• Schnorr dimension
  (with Rodney G. Downey and Jan Reimann). [PDF]
  Mathematical Structures in Computer Science, 16:789-811, 2006.
  Preliminary version in Computability in Europe 2005, LNCS 3526:96-105, Springer, 2005.
  

  ---

• Trees and learning [PDF]
  (with Frank Stephan).
  
  Journal of Computer and System Sciences 68:134-156, 2004.
  Preliminary version in Computational Learning Theory 1996 (COLT 1996), p. 270-79, ACM-Press, 1996.

  ---

• On the construction of effective random sets
  (with Nenad Mihailovic).
  
  Journal of Symbolic Logic 69:862-878, 2004.
  Preliminary version in Mathematical Foundations of Computer Science 2002, LNCS 2420:568-580, Springer, 2002.
  

  ---

• The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences.
  
  Journal of Symbolic Logic 68:1362-1376, 2003.
  Preliminary version in International Colloquium on Automata, Languages and Programming 2002, LNCS 2380:390-400, Springer, 2002.
  

  ---

• On the autoreducibility of random sequences [PS] [PDF]
  (with Todd Ebert and Heribert Vollmer).
  
  SIAM Journal on Computing 32:1542-1569, 2003.
  
  This article is a joint full version of the following conference articles.
  Todd Ebert and Heribert Vollmer, On the autoreducibility of random sequences,
  Mathematical Foundations of Computer Science 2000, LNCS 2000:333-343, Springer, 2000.
  Todd Ebert and Wolfgang Merkle, Autoreducibility of random sets: a sharp bound on the density of guessed bits,
  Mathematical Foundations of Computer Science 2002, LNCS 2420:221-233, Springer, 2002.

  ---

• Almost complete sets
  (with Klaus Ambos-Spies, Jan Reimann, and Sebastiaan A. Terwijn).
  
  Theoretical Computer Science 306:177-194, 2003.
  Preliminary version in Symposium on Theoretical Aspects of Computer Science 2000,
  LNCS 1770:419-430, Springer, 2000.

  ---

• Refuting learning revisited
  (with Frank Stephan).
  
  Theoretical Computer Science 298:145-177, 2003.
  Preliminary version in Algorithmic Learning Theory 2001, LNCS 2225:299-314, Springer, 2001.

  ---

• Lattice embeddings for abstract bounded reducibilities. [PS] [PDF]
  
  SIAM Journal on Computing 31:1119-1155, 2002.
  

  ---

• Hausdorff Dimension in Exponential Time
  (with Klaus Ambos-Spies, Jan Reimann, and Frank Stephan).
  
  Conference on Computational Complexity 2001, p. 210-217, IEEE Computer Society, 2001.

  ---

• The global power of additional queries to p-random oracles. [PS] [PDF]
  
  SIAM Journal on Computing 31:483-495, 2001.
  Preliminary Version in International Colloquium on Automata, Languages and Programming 2000, LNCS 1853:914-925, Springer, 2000.
  

  ---

• Structural properties of bounded relations with an application to NP optimization problems.
  
  Theoretical Computer Science 250(1-2):101-124, 2001.
  A preliminary version has been presented at the ASHCOMP-Workshop on approximation algorithms, Udine 1996.

  ---

• Separations by random oracles and Almost Classes for generalized reducibilities
  (with Yongge Wang).
  
  Mathematical Logic Quarterly 47:249-269, 2001.
  Preliminary version in Mathematical Foundations of Computer Science 1995,
  LNCS 969:179-190, Springer, 1995.

  ---

• Collapsing polynomial-time degrees
  (with Klaus Ambos-Spies, Levke Bentzien, Peter A. Fejer, and Frank Stephan).
  
  Logic Colloquium 1998, Lecture Notes in Logic 13:1-24,
  Association for Symbolic Logic, A.K. Peters, Ltd., 2000.
  

  ---

• Exact pairs for abstract bounded reducibilities.
  
  Mathematical Logic Quarterly 45:343-360, 1999.
  Preliminary version in Computer Science Logic 1996, LNCS 1258:349-68, Springer, 1997.

Survey articles and lecture notes

• Randomized Algorithms. [PS] [PDF]
  
  Lecture notes for a short course at the ESSLLI 2001 Summer School in Helsinki, version October 2001.
  
  

  ---

• Proving the PCP-theorem
  (with Volker Heun and Ulrich Weigand).
  
  Survey article in: Ernst W. Mayr, Hans Jürgen Prömel, and Angelika Steger (Eds.).
  Lectures on Proof Verfication and Approximation Algorithms. LNCS 1367:83-160, Springer, 1998.

Edited work

• Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings.
  (with Klaus Ambos-Spies and Benedikt Löwe; eds.).
  
  LNCS 5635, Springer, 2009.

Other writings

• A generalized account of resource bounded reducibilities.
  
  Doctoral Dissertation, Mathematische Fakultät, Ruprecht-Karls-Universität Heidelberg, 1997, 144 pages (corrected version 1997).

  ---

• Effective randomness [PS] [PDF].
  
  Habilitationsschrift, Fakultät für Mathematik und Informatik, Ruprecht-Karls-Universität Heidelberg, January 2004, 115 pages.