Klaus Ambos-Spies

89 papers A* 3A 9B 10C 7Journal 46Unranked 9
YearRankTypeTitle / Venue / Authors
2024 J jnl
Lowness properties for strong reducibilities and the computational power of maximal sets.
Comput.
Klaus Ambos-Spies, Rod Downey, Martin Monath
2022 J jnl
Normalized information distance and the oscillation hierarchy.
J. Comput. Syst. Sci.
Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn
2021 J jnl
On Supersets of non-low 22_2 Sets.
J. Symb. Log.
Klaus Ambos-Spies, Rodney G. Downey, Martin Monath
2021 — conf
Some Observations on Mitotic Sets.
Logic, Computation and Rigorous Methods
Klaus Ambos-Spies
2019 C conf
On the Differences and Sums of Strongly Computably Enumerable Real Numbers.
CiE
Klaus Ambos-Spies, Xizhong Zheng
2019 J jnl
Weak Completeness Notions for Exponential Time.
Theory Comput. Syst.
Klaus Ambos-Spies, Timur Bakibayev
2018 J jnl
Automorphism bases for the recursively enumerable degrees.
Comput.
Klaus Ambos-Spies
2018 C conf
Multiple Permitting and Array Noncomputability.
CiE
Klaus Ambos-Spies
2017 J jnl
Computability Theory (Dagstuhl Seminar 17081).
Dagstuhl Reports
Klaus Ambos-Spies, Vasco Brattka, Rodney G. Downey, Steffen Lempp
2017 J jnl
Normalized Information Distance and the Oscillation Hierarchy.
CoRR
Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn
2017 — conf
On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets.
Computability and Complexity
Klaus Ambos-Spies
2016 B conf
Learning Finite Variants of Single Languages from Informant.
ALT
Klaus Ambos-Spies
2014 — ch.
Degrees of Unsolvability.
Computational Logic
Klaus Ambos-Spies, Peter A. Fejer
2014 — ch.
On the strongly bounded turing degrees of simple sets.
Logic, Computation, Hierarchies
Klaus Ambos-Spies
2013 J jnl
Computability in Europe 2009.
J. Log. Comput.
Klaus Ambos-Spies, Arnold Beckmann, Erzsébet Csuhaj-Varjú, Benedikt Löwe
2013 J jnl
Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees.
Theory Comput. Syst.
Klaus Ambos-Spies, Decheng Ding, Yun Fan, Wolfgang Merkle
2013 J jnl
Nontriviality for exponential time w.r.t. weak reducibilities.
Theor. Comput. Sci.
Klaus Ambos-Spies, Timur Bakibayev
2013 J jnl
Preface.
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Joan Bagaria, Enrique Casanovas, Ulrich Kohlenbach
2013 C conf
Real Benefit of Promises and Advice.
CiE
Klaus Ambos-Spies, Ulrike Brandt, Martin Ziegler
2013 J jnl
The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent.
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Philipp Bodewig, Yun Fan, Thorsten Kräling
2012 J jnl
Comparing Nontriviality for E and EXP.
Theory Comput. Syst.
Klaus Ambos-Spies, Timur Bakibayev
2012 J jnl
Computability in Europe 2009.
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss, Benedikt Löwe
2011 J jnl
Inductive inference and computable numberings.
Theor. Comput. Sci.
Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey S. Goncharov
2010 C conf
Nontriviality for Exponential Time w.r.t. Weak Reducibilities.
TAMC
Klaus Ambos-Spies, Timur Bakibayev
2010 J jnl
Quantitative aspects of speed-up and gap phenomena.
Math. Struct. Comput. Sci.
Klaus Ambos-Spies, Thorsten Kräling
2010 — conf
Weak Completeness Notions for Exponential Time.
ICALP (1)
Klaus Ambos-Spies, Timur Bakibayev
2009 J jnl
Bounding non-GL
J. Symb. Log.
Klaus Ambos-Spies, Decheng Ding, Wei Wang, Liang Yu
2009 C ed.
Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings
CiE
Klaus Ambos-Spies, Benedikt Löwe, Wolfgang Merkle
2009 C conf
Quantitative Aspects of Speed-Up and Gap Phenomena.
TAMC
Klaus Ambos-Spies, Thorsten Kräling
2008 C conf
On a Question of Frank Stephan.
TAMC
Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey Goncharov
2004 J jnl
Comparing DNR and WWKL.
J. Symb. Log.
Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, Theodore A. Slaman
2004 B conf
Computational Aspects of Disjunctive Sequences.
MFCS
Klaus Ambos-Spies, Edgar Busse
2003 J jnl
Almost complete sets.
Theor. Comput. Sci.
Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan Terwijn
2003 — conf
Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata.
DMTCS
Klaus Ambos-Spies, Edgar Busse
2003 B conf
Problems with Cannot Be Reduced to Any Proper Subproblems.
MFCS
Klaus Ambos-Spies
2001 J jnl
Embedding of N
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Peter A. Fejer
2001 A conf
Hausdorff Dimension in Exponential Time.
CCC
Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan
2000 A conf
Almost Complete Sets.
STACS
Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan Terwijn
2000 B conf
Measure Theoretic Completeness Notions for the Exponential Time Classes.
MFCS
Klaus Ambos-Spies
2000 J jnl
Separating NP-Completeness Notions under Strong Hypotheses.
J. Comput. Syst. Sci.
Klaus Ambos-Spies, Levke Bentzien
2000 J jnl
Undecidability and 1-types in intervals of the computably enumerable degrees.
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Denis R. Hirschfeldt, Richard A. Shore
2000 J jnl
Weakly Computable Real Numbers.
J. Complex.
Klaus Ambos-Spies, Klaus Weihrauch, Xizhong Zheng
1999 — ch.
Polynomial Time Reducibilities and Degrees.
Handbook of Computability Theory
Klaus Ambos-Spies
1998 B conf
Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets.
MFCS
Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt
1997 J jnl
Resource Bounded Randomness and Weakly Complete Problems.
Theor. Comput. Sci.
Klaus Ambos-Spies, Sebastiaan Terwijn, Xizhong Zheng
1997 A conf
Separating NP-Completeness Notions under Strong Hypotheses.
CCC
Klaus Ambos-Spies, Levke Bentzien
1996 A conf
A Comparison of Weak Completeness Notions.
CCC
Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng
1996 J jnl
Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices.
J. Symb. Log.
Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp, Manuel Lerman
1996 J jnl
Genericity and Measure for Exponential Time.
Theor. Comput. Sci.
Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan Terwijn
1996 A conf
Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness.
STACS
Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng
1995 A* conf
On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (Extended Abstract).
ICALP
Klaus Ambos-Spies
1995 — conf
Resource-Bounded Genericity.
SCT
Klaus Ambos-Spies
1994 J jnl
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees.
Math. Log. Q.
Decheng Ding, Klaus Ambos-Spies
1994 B conf
Genericity and Measure for Exponential Time.
MFCS
Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan Terwijn
1994 J jnl
Minimal Pairs and Complete Problems.
Theor. Comput. Sci.
Klaus Ambos-Spies, Steven Homer, Robert I. Soare
1994 B conf
Resource Bounded Randomness and Weakly Complete Problems.
ISAAC
Klaus Ambos-Spies, Sebastiaan Terwijn, Xizhong Zheng
1993 — ed.
Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992
Complexity Theory: Current Research
Klaus Ambos-Spies, Steven Homer, Uwe Schöning
1993 J jnl
The Continuity of Cupping to 0'.
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Alistair H. Lachlan, Robert I. Soare
1993 J jnl
Undecidability and 1-Types in the Recursively Enumerable Degrees.
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Richard A. Shore
1992 J jnl
Cappable recursively enumerable degrees and Post's program.
Arch. Math. Log.
Klaus Ambos-Spies, André Nies
1992 A conf
The Theory of the Polynomial Many-One Degrees of Recursive Sets is Undecidable.
STACS
Klaus Ambos-Spies, André Nies
1992 J jnl
The Theory of the Recursively Enumerable Weak Truth-Table Degrees Is Undecidability.
J. Symb. Log.
Klaus Ambos-Spies, André Nies, Richard A. Shore
1990 A conf
Minimal Pairs and Complete Problems.
STACS
Klaus Ambos-Spies, Steven Homer, Robert I. Soare
1989 J jnl
Honest Polynomial Time Reducibilities and the P = ? NP Problem.
J. Comput. Syst. Sci.
Klaus Ambos-Spies
1989 B conf
Honest Polynomial-Time Degrees of Elementary Recursive Sets.
CSL
Klaus Ambos-Spies, Dongping Yang
1989 J jnl
Lattice Embeddings into the Recursively Enumerable Degrees II.
J. Symb. Log.
Klaus Ambos-Spies, Manuel Lerman
1989 J jnl
On the Relative Complexity of Hard Problems for Complexity Classes without Complete Problems.
Theor. Comput. Sci.
Klaus Ambos-Spies
1989 J jnl
The Recursively Enumerable Degrees have Infinitely Many One-Types.
Ann. Pure Appl. Log.
Klaus Ambos-Spies, Robert I. Soare
1988 J jnl
Degree Theoretical Splitting Properties of Recursively Enumerable Sets.
J. Symb. Log.
Klaus Ambos-Spies, Peter A. Fejer
1988 B conf
On Disjunctive Self-Reducibility.
CSL
Klaus Ambos-Spies, Jürgen Kämper
1987 J jnl
Diagonalizations over Polynomial Time Computable Sets.
Theor. Comput. Sci.
Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig
1987 B conf
Diagonalizing over Deterministic Polynomial Time.
CSL
Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig
1987 — conf
Honest polynomial reducibilities, recursively enumerable sets, and the P=?NP problem.
SCT
Klaus Ambos-Spies
1987 — conf
Minimal Pairs for Polynomial Time Reducibilities.
Computation Theory and Logic
Klaus Ambos-Spies
1986 J jnl
A Note on the Complete Problems for Complexity Classes.
Inf. Process. Lett.
Klaus Ambos-Spies
1986 J jnl
An Inhomogeneity in the Structure of Karp Degrees.
SIAM J. Comput.
Klaus Ambos-Spies
1986 J jnl
Inhomogeneities in the Polynomial-Time Degrees: The Degrees of Super Sparse Sets.
Inf. Process. Lett.
Klaus Ambos-Spies
1986 J jnl
Lattice Embeddings into the Recursively Enumerable Degrees.
J. Symb. Log.
Klaus Ambos-Spies, Manuel Lerman
1986 — conf
Randomness, Relativizations, and Polynomial Reducibilities.
SCT
Klaus Ambos-Spies
1985 J jnl
Anti-Mitotic Recursively Enumerable Sets.
Math. Log. Q.
Klaus Ambos-Spies
1985 J jnl
Cupping and noncapping in the r.e. weak truth table and turing degrees.
Arch. Math. Log.
Klaus Ambos-Spies
1985 A conf
On the Relative Complexity of Subproblems of Intractable Problems.
STACS
Klaus Ambos-Spies
1985 — —
On the structure of the polynomial time degrees of recursive sets.
Klaus Ambos-Spies
1985 J jnl
Sublattices of the Polynomial Time Degrees
Inf. Control.
Klaus Ambos-Spies
1985 A* conf
Three Theorems on Polynomial Degrees of NP-Sets
FOCS
Klaus Ambos-Spies
1984 J jnl
An Extension of the Nondiamond Theorem in Classical and alpha-Recursion Theory.
J. Symb. Log.
Klaus Ambos-Spies
1984 A conf
On the Structure of Polynomial Time Degrees.
STACS
Klaus Ambos-Spies
1984 A* conf
P-Generic Sets.
ICALP
Klaus Ambos-Spies
1983 — conf
P-mitotic sets.
Logic and Machines
Klaus Ambos-Spies