Klaus Ambos-Spies

According to our database, Klaus Ambos-Spies authored at least 78 papers between 1983 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Lowness properties for strong reducibilities and the computational power of maximal sets.

Klaus Ambos-Spies, Rod Downey, Martin Monath

Comput., 2024

2022

Normalized information distance and the oscillation hierarchy.

Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn

J. Comput. Syst. Sci., 2022

2021

On Supersets of non-low 22_2 Sets.

Klaus Ambos-Spies, Rodney G. Downey, Martin Monath

J. Symb. Log., 2021

Some Observations on Mitotic Sets.

Klaus Ambos-Spies

Proceedings of the Logic, Computation and Rigorous Methods, 2021

2019

Weak Completeness Notions for Exponential Time.

Klaus Ambos-Spies, Timur Bakibayev

Theory Comput. Syst., 2019

On the Differences and Sums of Strongly Computably Enumerable Real Numbers.

Klaus Ambos-Spies, Xizhong Zheng

Proceedings of the Computing with Foresight and Industry, 2019

2018

Automorphism bases for the recursively enumerable degrees.

Klaus Ambos-Spies

Comput., 2018

Multiple Permitting and Array Noncomputability.

Klaus Ambos-Spies

Proceedings of the Sailing Routes in the World of Computation, 2018

2017

Computability Theory (Dagstuhl Seminar 17081).

Klaus Ambos-Spies, Vasco Brattka, Rodney G. Downey, Steffen Lempp

Dagstuhl Reports, 2017

On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets.

Klaus Ambos-Spies

Proceedings of the Computability and Complexity, 2017

2016

Learning Finite Variants of Single Languages from Informant.

Klaus Ambos-Spies

Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

2014

Degrees of Unsolvability.

Klaus Ambos-Spies, Peter A. Fejer

Proceedings of the Computational Logic, 2014

On the strongly bounded turing degrees of simple sets.

Klaus Ambos-Spies

Proceedings of the Logic, Computation, Hierarchies, 2014

2013

Nontriviality for exponential time w.r.t. weak reducibilities.

Klaus Ambos-Spies, Timur Bakibayev

Theor. Comput. Sci., 2013

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

Klaus Ambos-Spies, Decheng Ding, Yun Fan, Wolfgang Merkle

Theory Comput. Syst., 2013

Computability in Europe 2009.

Klaus Ambos-Spies, Arnold Beckmann, Erzsébet Csuhaj-Varjú, Benedikt Löwe

J. Log. Comput., 2013

The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent.

Klaus Ambos-Spies, Philipp Bodewig, Yun Fan, Thorsten Kräling

Ann. Pure Appl. Log., 2013

Preface.

Klaus Ambos-Spies, Joan Bagaria, Enrique Casanovas, Ulrich Kohlenbach

Ann. Pure Appl. Log., 2013

Real Benefit of Promises and Advice.

Klaus Ambos-Spies, Ulrike Brandt, Martin Ziegler

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

2012

Comparing Nontriviality for E and EXP.

Klaus Ambos-Spies, Timur Bakibayev

Theory Comput. Syst., 2012

Computability in Europe 2009.

Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss, Benedikt Löwe

Ann. Pure Appl. Log., 2012

2011

Inductive inference and computable numberings.

Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey S. Goncharov

Theor. Comput. Sci., 2011

2010

Quantitative aspects of speed-up and gap phenomena.

Klaus Ambos-Spies, Thorsten Kräling

Math. Struct. Comput. Sci., 2010

2009

Bounding non-GL₂ and R.E.A.

Klaus Ambos-Spies, Decheng Ding, Wei Wang, Liang Yu

J. Symb. Log., 2009

2008

On a Question of Frank Stephan.

Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey Goncharov

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

2004

Comparing DNR and WWKL.

Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, Theodore A. Slaman

J. Symb. Log., 2004

Computational Aspects of Disjunctive Sequences.

Klaus Ambos-Spies, Edgar Busse

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003

Almost complete sets.

Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan Terwijn

Theor. Comput. Sci., 2003

Problems with Cannot Be Reduced to Any Proper Subproblems.

Klaus Ambos-Spies

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata.

Klaus Ambos-Spies, Edgar Busse

Proceedings of the Discrete Mathematics and Theoretical Computer Science, 2003

2001

Embedding of N₅ and the contiguous degrees.

Klaus Ambos-Spies, Peter A. Fejer

Ann. Pure Appl. Log., 2001

Hausdorff Dimension in Exponential Time.

Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Frank Stephan

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

2000

Separating NP-Completeness Notions under Strong Hypotheses.

Klaus Ambos-Spies, Levke Bentzien

J. Comput. Syst. Sci., 2000

Weakly Computable Real Numbers.

Klaus Ambos-Spies, Klaus Weihrauch, Xizhong Zheng

J. Complex., 2000

Undecidability and 1-types in intervals of the computably enumerable degrees.

Klaus Ambos-Spies, Denis R. Hirschfeldt, Richard A. Shore

Ann. Pure Appl. Log., 2000

Measure Theoretic Completeness Notions for the Exponential Time Classes.

Klaus Ambos-Spies

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999

Polynomial Time Reducibilities and Degrees.

Klaus Ambos-Spies

Proceedings of the Handbook of Computability Theory, 1999

1998

Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets.

Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

Resource Bounded Randomness and Weakly Complete Problems.

Klaus Ambos-Spies, Sebastiaan Terwijn, Xizhong Zheng

Theor. Comput. Sci., 1997

1996

Genericity and Measure for Exponential Time.

Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan Terwijn

Theor. Comput. Sci., 1996

Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices.

Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp, Manuel Lerman

J. Symb. Log., 1996

Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness.

Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng

Proceedings of the STACS 96, 1996

A Comparison of Weak Completeness Notions.

Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (Extended Abstract).

Klaus Ambos-Spies

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Resource-Bounded Genericity.

Klaus Ambos-Spies

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Minimal Pairs and Complete Problems.

Klaus Ambos-Spies, Steven Homer, Robert I. Soare

Theor. Comput. Sci., 1994

Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees.

Decheng Ding, Klaus Ambos-Spies

Math. Log. Q., 1994

1993

Undecidability and 1-Types in the Recursively Enumerable Degrees.

Klaus Ambos-Spies, Richard A. Shore

Ann. Pure Appl. Log., 1993

The Continuity of Cupping to 0'.

Klaus Ambos-Spies, Alistair H. Lachlan, Robert I. Soare

Ann. Pure Appl. Log., 1993

1992

The Theory of the Recursively Enumerable Weak Truth-Table Degrees Is Undecidability.

Klaus Ambos-Spies, André Nies, Richard A. Shore

J. Symb. Log., 1992

Cappable recursively enumerable degrees and Post's program.

Klaus Ambos-Spies, André Nies

Arch. Math. Log., 1992

The Theory of the Polynomial Many-One Degrees of Recursive Sets is Undecidable.

Klaus Ambos-Spies, André Nies

Proceedings of the STACS 92, 1992

1989

On the Relative Complexity of Hard Problems for Complexity Classes without Complete Problems.

Klaus Ambos-Spies

Theor. Comput. Sci., 1989

Lattice Embeddings into the Recursively Enumerable Degrees II.

Klaus Ambos-Spies, Manuel Lerman

J. Symb. Log., 1989

Honest Polynomial Time Reducibilities and the P = ? NP Problem.

Klaus Ambos-Spies

J. Comput. Syst. Sci., 1989

The Recursively Enumerable Degrees have Infinitely Many One-Types.

Klaus Ambos-Spies, Robert I. Soare

Ann. Pure Appl. Log., 1989

Honest Polynomial-Time Degrees of Elementary Recursive Sets.

Klaus Ambos-Spies, Dongping Yang

Proceedings of the CSL '89, 1989

1988

Degree Theoretical Splitting Properties of Recursively Enumerable Sets.

Klaus Ambos-Spies, Peter A. Fejer

J. Symb. Log., 1988

On Disjunctive Self-Reducibility.

Klaus Ambos-Spies, Jürgen Kämper

Proceedings of the CSL '88, 1988

1987

Diagonalizations over Polynomial Time Computable Sets.

Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig

Theor. Comput. Sci., 1987

Diagonalizing over Deterministic Polynomial Time.

Klaus Ambos-Spies, Hans Fleischhack, Hagen Huwig

Proceedings of the CSL '87, 1987

Honest polynomial reducibilities, recursively enumerable sets, and the P=?NP problem.

Klaus Ambos-Spies

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

Minimal Pairs for Polynomial Time Reducibilities.

Klaus Ambos-Spies

Proceedings of the Computation Theory and Logic, In Memory of Dieter Rödding, 1987

1986

An Inhomogeneity in the Structure of Karp Degrees.

Klaus Ambos-Spies

SIAM J. Comput., 1986

Lattice Embeddings into the Recursively Enumerable Degrees.

Klaus Ambos-Spies, Manuel Lerman

J. Symb. Log., 1986

A Note on the Complete Problems for Complexity Classes.

Klaus Ambos-Spies

Inf. Process. Lett., 1986

Inhomogeneities in the Polynomial-Time Degrees: The Degrees of Super Sparse Sets.

Klaus Ambos-Spies

Inf. Process. Lett., 1986

Randomness, Relativizations, and Polynomial Reducibilities.

Klaus Ambos-Spies

Proceedings of the Structure in Complexity Theory, 1986

1985

Sublattices of the Polynomial Time Degrees

Klaus Ambos-Spies

Inf. Control., April, 1985

Anti-Mitotic Recursively Enumerable Sets.

Klaus Ambos-Spies

Math. Log. Q., 1985

Cupping and noncapping in the r.e. weak truth table and turing degrees.

Klaus Ambos-Spies

Arch. Math. Log., 1985

On the Relative Complexity of Subproblems of Intractable Problems.

Klaus Ambos-Spies

Proceedings of the STACS 85, 1985

Three Theorems on Polynomial Degrees of NP-Sets

Klaus Ambos-Spies

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

On the structure of the polynomial time degrees of recursive sets.

Klaus Ambos-Spies

PhD thesis, 1985

1984

An Extension of the Nondiamond Theorem in Classical and alpha-Recursion Theory.

Klaus Ambos-Spies

J. Symb. Log., 1984

On the Structure of Polynomial Time Degrees.

Klaus Ambos-Spies

Proceedings of the STACS 84, 1984

P-Generic Sets.

Klaus Ambos-Spies

Proceedings of the Automata, 1984

1983

P-mitotic sets.

Klaus Ambos-Spies

Proceedings of the Logic and Machines: Decision Problems and Complexity, 1983