Klaus Ambos-Spies

Orcid: 0000-0003-4898-7505

Affiliations:
  • Heidelberg University, Germany


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

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

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

2021
On Supersets of non-low 22_2 Sets.
J. Symb. Log., 2021

Some Observations on Mitotic Sets.
Proceedings of the Logic, Computation and Rigorous Methods, 2021

2019
Weak Completeness Notions for Exponential Time.
Theory Comput. Syst., 2019

On the Differences and Sums of Strongly Computably Enumerable Real Numbers.
Proceedings of the Computing with Foresight and Industry, 2019

2018
Automorphism bases for the recursively enumerable degrees.
Comput., 2018

Multiple Permitting and Array Noncomputability.
Proceedings of the Sailing Routes in the World of Computation, 2018

2017
Computability Theory (Dagstuhl Seminar 17081).
Dagstuhl Reports, 2017

On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets.
Proceedings of the Computability and Complexity, 2017

2016
Learning Finite Variants of Single Languages from Informant.
Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

2014
Degrees of Unsolvability.
Proceedings of the Computational Logic, 2014

On the strongly bounded turing degrees of simple sets.
Proceedings of the Logic, Computation, Hierarchies, 2014

2013
Nontriviality for exponential time w.r.t. weak reducibilities.
Theor. Comput. Sci., 2013

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

Computability in Europe 2009.
J. Log. Comput., 2013

The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent.
Ann. Pure Appl. Log., 2013

Preface.
Ann. Pure Appl. Log., 2013

Real Benefit of Promises and Advice.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

2012
Comparing Nontriviality for E and EXP.
Theory Comput. Syst., 2012

Computability in Europe 2009.
Ann. Pure Appl. Log., 2012

2011
Inductive inference and computable numberings.
Theor. Comput. Sci., 2011

2010
Quantitative aspects of speed-up and gap phenomena.
Math. Struct. Comput. Sci., 2010

2009
Bounding non-GL<sub>2</sub> and R.E.A.
J. Symb. Log., 2009

2008
On a Question of Frank Stephan.
Proceedings of the Theory and Applications of Models of Computation, 2008

2004
Comparing DNR and WWKL.
J. Symb. Log., 2004

Computational Aspects of Disjunctive Sequences.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

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

Problems with Cannot Be Reduced to Any Proper Subproblems.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata.
Proceedings of the Discrete Mathematics and Theoretical Computer Science, 2003

2001
Embedding of N<sub>5</sub> and the contiguous degrees.
Ann. Pure Appl. Log., 2001

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

2000
Separating NP-Completeness Notions under Strong Hypotheses.
J. Comput. Syst. Sci., 2000

Weakly Computable Real Numbers.
J. Complex., 2000

Undecidability and 1-types in intervals of the computably enumerable degrees.
Ann. Pure Appl. Log., 2000

Measure Theoretic Completeness Notions for the Exponential Time Classes.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999
Polynomial Time Reducibilities and Degrees.
Proceedings of the Handbook of Computability Theory, 1999

1998
Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997
Resource Bounded Randomness and Weakly Complete Problems.
Theor. Comput. Sci., 1997

1996
Genericity and Measure for Exponential Time.
Theor. Comput. Sci., 1996

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

Resource-Bounded Balanced Genericity, Stochasticity and Weak Randomness.
Proceedings of the STACS 96, 1996

A Comparison of Weak Completeness Notions.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Resource-Bounded Genericity.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
Minimal Pairs and Complete Problems.
Theor. Comput. Sci., 1994

Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees.
Math. Log. Q., 1994

1993
Undecidability and 1-Types in the Recursively Enumerable Degrees.
Ann. Pure Appl. Log., 1993

The Continuity of Cupping to 0'.
Ann. Pure Appl. Log., 1993

1992
The Theory of the Recursively Enumerable Weak Truth-Table Degrees Is Undecidability.
J. Symb. Log., 1992

Cappable recursively enumerable degrees and Post's program.
Arch. Math. Log., 1992

The Theory of the Polynomial Many-One Degrees of Recursive Sets is Undecidable.
Proceedings of the STACS 92, 1992

1989
On the Relative Complexity of Hard Problems for Complexity Classes without Complete Problems.
Theor. Comput. Sci., 1989

Lattice Embeddings into the Recursively Enumerable Degrees II.
J. Symb. Log., 1989

Honest Polynomial Time Reducibilities and the P = ? NP Problem.
J. Comput. Syst. Sci., 1989

The Recursively Enumerable Degrees have Infinitely Many One-Types.
Ann. Pure Appl. Log., 1989

Honest Polynomial-Time Degrees of Elementary Recursive Sets.
Proceedings of the CSL '89, 1989

1988
Degree Theoretical Splitting Properties of Recursively Enumerable Sets.
J. Symb. Log., 1988

On Disjunctive Self-Reducibility.
Proceedings of the CSL '88, 1988

1987
Diagonalizations over Polynomial Time Computable Sets.
Theor. Comput. Sci., 1987

Diagonalizing over Deterministic Polynomial Time.
Proceedings of the CSL '87, 1987

Honest polynomial reducibilities, recursively enumerable sets, and the P=?NP problem.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

Minimal Pairs for Polynomial Time Reducibilities.
Proceedings of the Computation Theory and Logic, In Memory of Dieter Rödding, 1987

1986
An Inhomogeneity in the Structure of Karp Degrees.
SIAM J. Comput., 1986

Lattice Embeddings into the Recursively Enumerable Degrees.
J. Symb. Log., 1986

A Note on the Complete Problems for Complexity Classes.
Inf. Process. Lett., 1986

Inhomogeneities in the Polynomial-Time Degrees: The Degrees of Super Sparse Sets.
Inf. Process. Lett., 1986

Randomness, Relativizations, and Polynomial Reducibilities.
Proceedings of the Structure in Complexity Theory, 1986

1985
Sublattices of the Polynomial Time Degrees
Inf. Control., April, 1985

Anti-Mitotic Recursively Enumerable Sets.
Math. Log. Q., 1985

Cupping and noncapping in the r.e. weak truth table and turing degrees.
Arch. Math. Log., 1985

On the Relative Complexity of Subproblems of Intractable Problems.
Proceedings of the STACS 85, 1985

Three Theorems on Polynomial Degrees of NP-Sets
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

On the structure of the polynomial time degrees of recursive sets.
PhD thesis, 1985

1984
An Extension of the Nondiamond Theorem in Classical and alpha-Recursion Theory.
J. Symb. Log., 1984

On the Structure of Polynomial Time Degrees.
Proceedings of the STACS 84, 1984

P-Generic Sets.
Proceedings of the Automata, 1984

1983
P-mitotic sets.
Proceedings of the Logic and Machines: Decision Problems and Complexity, 1983


  Loading...