2024
Computability and Complexity - Foundations and Tools for Pursuing Scientific Applications
Undergraduate Topics in Computer Science, Springer, ISBN: 978-3-031-53743-1, 2024
ON THE C.E. DEGREES REALIZABLE IN $\Pi ^0_1$ CLASSES.
J. Symb. Log., 2024
Algorithmically random series.
Comput., 2024
Lowness properties for strong reducibilities and the computational power of maximal sets.
Comput., 2024
Some Open Questions and Recent Results on Computable Banach Spaces.
Proceedings of the Twenty Years of Theoretical and Practical Synergies, 2024
2023
Online, computable and punctual structure theory.
Log. J. IGPL, November, 2023
Computably Compact Metric Spaces.
Bull. Symb. Log., June, 2023
2022
A Minimal Set Low for Speed.
J. Symb. Log., December, 2022
Relationships between Computability-Theoretic Properties of Problems.
J. Symb. Log., 2022
2021
Foundations of Online Structure Theory II: The Operator Approach.
Log. Methods Comput. Sci., 2021
On Supersets of non-low 22_2 Sets.
J. Symb. Log., 2021
Maximality and collapse in the hierarchy of <i>α</i>-c.a. degrees.
Comput., 2021
2020
Punctual Categoricity and Universality.
J. Symb. Log., 2020
Graphs are not universal for online computability.
J. Comput. Syst. Sci., 2020
On low for speed oracles.
J. Comput. Syst. Sci., 2020
Computable Analysis and Classification Problems.
Proceedings of the Beyond the Horizon of Computability, 2020
2019
Martin-Löf Randomness Implies Multiple Recurrence in Effectively Closed Sets.
Notre Dame J. Formal Log., 2019
A Weakly 2-Generic which Bounds a Minimal degree.
J. Symb. Log., 2019
Splitting theorems and low degrees.
Comput., 2019
Preface of the special issue for the Oberwolfach Workshop on Computability Theory 2018.
Comput., 2019
Foundations of Online Structure Theory.
Bull. Symb. Log., 2019
Categorical linearly ordered structures.
Ann. Pure Appl. Log., 2019
2018
Theory Comput. Syst., 2018
Avoiding Effective Packing Dimension 1 below array Noncomputable C.E. Degrees.
J. Symb. Log., 2018
Degrees containing members of thin Π10 classes are dense and co-dense.
J. Math. Log., 2018
A Hierarchy of computably Enumerable Degrees.
Bull. Symb. Log., 2018
Splitting into degrees with low computational strength.
Ann. Pure Appl. Log., 2018
2017
Lowness and logical depth.
Theor. Comput. Sci., 2017
Kobayashi compressibility.
Theor. Comput. Sci., 2017
Logic and Computational Complexity (NII Shonan Meeting 2017-13).
NII Shonan Meet. Rep., 2017
Notes on Computable Analysis.
Theory Comput. Syst., 2017
A Friedberg enumeration of equivalence structures.
J. Math. Log., 2017
Courcelle's theorem for triangulations.
J. Comb. Theory A, 2017
Computability Theory (Dagstuhl Seminar 17081).
Dagstuhl Reports, 2017
Proceedings of the Turing Guide., 2017
2016
Abelian p-groups and the Halting problem.
Ann. Pure Appl. Log., 2016
2015
Asymptotic density and the Ershov hierarchy.
Math. Log. Q., 2015
Solovay functions and their applications in algorithmic randomness.
J. Comput. Syst. Sci., 2015
Integer valued betting strategies and Turing degrees.
J. Comput. Syst. Sci., 2015
The members of thin and minimal classes, their ranks and Turing degrees.
Ann. Pure Appl. Log., 2015
On -categoricity of equivalence relations.
Ann. Pure Appl. Log., 2015
Myhill-Nerode Methods for Hypergraphs.
Algorithmica, 2015
2014
Algorithmic Randomness and Complexity (NII Shonan Meeting 2014-10).
NII Shonan Meet. Rep., 2014
Characterizing Lowness for Demuth Randomness.
J. Symb. Log., 2014
Exact Pairs for the Ideal of the <i>k</i>-Trivial Sequences in the Turing Degrees.
J. Symb. Log., 2014
Iterated effective embeddings of abelian p-groups.
Int. J. Algebra Comput., 2014
Random strings and tt-degrees of Turing complete C.E. sets.
Log. Methods Comput. Sci., 2014
Computability theory, algorithmic randomness and Turing's anticipation.
Proceedings of the Turing's Legacy: Developments from Turing's Ideas in Logic, 2014
2013
Fundamentals of Parameterized Complexity.
Texts in Computer Science, Springer, ISBN: 978-1-4471-5559-1, 2013
Computability, Complexity and Randomness.
Theory Comput. Syst., 2013
Asymptotic density and computably Enumerable Sets.
J. Math. Log., 2013
2012
Lowness for bounded randomness.
Theor. Comput. Sci., 2012
Computability, Complexity and Randomness (Dagstuhl Seminar 12021).
Dagstuhl Reports, 2012
A Parameterized Complexity Tutorial.
Proceedings of the Language and Automata Theory and Applications, 2012
Randomness, Computation and Mathematics.
Proceedings of the How the World Computes, 2012
A Basic Parameterized Complexity Primer.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012
The Birth and Early Years of Parameterized Complexity.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012
Proceedings of the Computation, Physics and Beyond, 2012
2011
Euclidean Functions of Computable Euclidean Domains.
Notre Dame J. Formal Log., 2011
Limits on jump inversion for strong reducibilities.
J. Symb. Log., 2011
Jump inversions inside effectively closed sets and applications to randomness.
J. Symb. Log., 2011
Confronting intractability via parameters.
Comput. Sci. Rev., 2011
Binary subtrees with few labeled paths.
Comb., 2011
2010
Effective Packing Dimension and Traceability.
Notre Dame J. Formal Log., 2010
Decidability and Computability of Certain Torsion-Free Abelian Groups.
Notre Dame J. Formal Log., 2010
On the Complexity of the Successivity Relation in Computable linear Orderings.
J. Math. Log., 2010
Algorithmic Randomness and Complexity.
Theory and Applications of Computability, Springer, ISBN: 978-0-387-95567-4, 2010
2009
On computable self-embeddings of computable linear orderings.
J. Symb. Log., 2009
On problems without polynomial kernels.
J. Comput. Syst. Sci., 2009
Space complexity of Abelian groups.
Arch. Math. Log., 2009
Kolmogorov Complexity and Solovay Functions.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009
Lowness for Demuth Randomness.
Proceedings of the Mathematical Theory and Computational Practice, 2009
2008
Turing degrees of reals of positive effective packing dimension.
Inf. Process. Lett., 2008
Parameterized approximation of dominating set problems.
Inf. Process. Lett., 2008
The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors.
Comput. J., 2008
The Complexity of Orbits of Computably Enumerable Sets.
Bull. Symb. Log., 2008
The upward closure of a perfect thin class.
Ann. Pure Appl. Log., 2008
On Problems without Polynomial Kernels (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
2007
Theory Comput. Syst., 2007
Totally ω-computably Enumerable Degrees and Bounding Critical Triples.
J. Math. Log., 2007
Online promise problems with online width metrics.
J. Comput. Syst. Sci., 2007
Undecidability of the structure of the Solovay degrees of c.e. reals.
J. Comput. Syst. Sci., 2007
Bounded fixed-parameter tractability and reducibility.
Ann. Pure Appl. Log., 2007
07441 Abstracts Collection -- Algorithmic-Logical Theory of Infinite Structures.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007
07441 Summary -- Algorithmic-Logical Theory of Infinite Structures.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007
2006
Theor. Comput. Sci., 2006
Math. Struct. Comput. Sci., 2006
Lowness and Π<sub>2</sub><sup>0</sup> nullsets.
J. Symb. Log., 2006
Every 1-generic computes a properly 1-generic.
J. Symb. Log., 2006
On self-embeddings of computable linear orderings.
Ann. Pure Appl. Log., 2006
Ann. Pure Appl. Log., 2006
Arithmetical Sacks Forcing.
Arch. Math. Log., 2006
Totally < ω<sup>ω</sup> Computably Enumerable and <i>m</i>-topped Degrees.
Proceedings of the Theory and Applications of Models of Computation, 2006
Parameterized Approximation Problems.
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006
2005
Relativizing Chaitin's Halting Probability.
J. Math. Log., 2005
Completing pseudojump operators.
Ann. Pure Appl. Log., 2005
05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability.
Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005
05301 Summary - Exact Algorithms and Fixed-Parameter Tractability.
Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005
Bounded Persistence Pathwidth.
Proceedings of the Theory of Computing 2005, 2005
2004
Theor. Comput. Sci., 2004
There Are No Maximal Low D.C.E. Degrees.
Notre Dame J. Formal Log., 2004
Degrees of d. c. e. reals.
Math. Log. Q., 2004
On Schnorr and computable randomness, martingales, and machines.
Math. Log. Q., 2004
Randomness and reducibility.
J. Comput. Syst. Sci., 2004
The Kolmogorov complexity of random reals.
Ann. Pure Appl. Log., 2004
Complementing cappable degrees in the difference hierarchy.
Ann. Pure Appl. Log., 2004
Some Recent Progress in Algorithmic Randomness.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004
Online Problems, Pathwidth, and Persistence.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004
Some New Directions and Questions in Parameterized Complexity.
Proceedings of the Developments in Language Theory, 2004
2003
Uniformly hard languages.
Theor. Comput. Sci., 2003
Decomposition and infima in the computably enumerable degrees.
J. Symb. Log., 2003
Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems.
Proceedings of the Computing: the Australasian Theory Symposiumm, 2003
2002
Presentations of computably enumerable reals.
Theor. Comput. Sci., 2002
Randomness, Computability, and Density.
SIAM J. Comput., 2002
Roman Murawski, Recursive Functions and Metamathematics.
Stud Logica, 2002
Computably Enumerable Reals and Uniformly Presentable Ideals.
Math. Log. Q., 2002
Contiguity and Distributivity in The Enumerable Turing Degrees - Corrigendum.
J. Symb. Log., 2002
Maximal Contiguous Degrees.
J. Symb. Log., 2002
Proceedings of the Computability and Complexity in Analysis, 2002
2001
On Genericity and Ershov's Hierarchy.
Math. Log. Q., 2001
A delta<sup>0</sup><sub>2</sub> Set with No Infinite Low Subset in Either It or Its Complement.
J. Symb. Log., 2001
Ann. Pure Appl. Log., 2001
Index sets and parametric reductions.
Arch. Math. Log., 2001
2000
On computing graph minor obstruction sets.
Theor. Comput. Sci., 2000
Undecidability Results for Low Complexity Time Classes.
J. Comput. Syst. Sci., 2000
The complexity of irredundant sets parameterized by size.
Discret. Appl. Math., 2000
1999
Monographs in Computer Science, Springer, ISBN: 038794883X, 1999
The Parametrized Complexity of Some Fundamental Problems in Coding Theory.
SIAM J. Comput., 1999
A Delta<sup>0</sup><sub>2</sub> Set With Barely Sigma<sup>0</sup><sub>2</sub> Degree.
J. Symb. Log., 1999
Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank 1.
J. Symb. Log., 1999
Computational Tractability: The View From Mars.
Bull. EATCS, 1999
Addendum to "Computably Enumerable Sets and Quasi-Reducibility".
Ann. Pure Appl. Log., 1999
1998
Parameterized Circuit Complexity and the W Hierarchy.
Theor. Comput. Sci., 1998
Threshold Dominating Sets and an Improved Characterization of <i>W</i>[2].
Theor. Comput. Sci., 1998
Splitting Theorems and the Jump Operator.
Ann. Pure Appl. Log., 1998
Computably Enumerable Sets and Quasi-Reducibility.
Ann. Pure Appl. Log., 1998
Difference Sets and Computability Theory.
Ann. Pure Appl. Log., 1998
1997
Infima in the Recursively Enumerable Weak Truth Table Degrees.
Notre Dame J. Formal Log., 1997
On the Universal Splitting Property.
Math. Log. Q., 1997
A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals.
J. Univers. Comput. Sci., 1997
Contiguity and Distributivity in the Enumerable Turing Degrees.
J. Symb. Log., 1997
Advice Classes of Parameterized Tractability.
Ann. Pure Appl. Log., 1997
On the parameterized complexity of short computation and factorization.
Arch. Math. Log., 1997
Parameterized complexity: A framework for systematically confronting computational intractability.
Proceedings of the Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 1997
Undecidability Results for Low Complexity Degree Structures.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997
1996
Ann. Pure Appl. Log., 1996
The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1].
Proceedings of the First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, 1996
Descriptive complexity and the <i>W</i> hierarchy.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996
1995
Fixed-Parameter Tractability and Completeness II: On Completeness for W[1].
Theor. Comput. Sci., 1995
The Parameterized Complexity of Sequence Alignment and Consensus.
Theor. Comput. Sci., 1995
Fixed-Parameter Tractability and Completeness I: Basic Results.
SIAM J. Comput., 1995
Degree Theoretic Definitions of the low<sub>2</sub> Recursively Enumerable Sets.
J. Symb. Log., 1995
On the Structure of Parameterized Problems in NP.
Inf. Comput., 1995
Parameterized complexity analysis in computational biology.
Comput. Appl. Biosci., 1995
Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues.
Ann. Pure Appl. Log., 1995
Intervals Without Critical Triples.
Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, 1995
1994
Embedding Lattices into the wtt-Degrees below 0'.
J. Symb. Log., 1994
Ann. Pure Appl. Log., 1994
The Structure of the Honest Polynomial m-Degrees.
Ann. Pure Appl. Log., 1994
There is no plus-capping degree.
Arch. Math. Log., 1994
On the Structure of Parameterized Problems in NP (Extended Abstract).
Proceedings of the STACS 94, 1994
The Parameterized Complexity of Some Problems in Logic and Linguistics.
Proceedings of the Logical Foundations of Computer Science, Third International Symposium, 1994
1993
Highness and Bounding Minimal Pairs.
Math. Log. Q., 1993
On the Cantor-Bendixon Rank of Recursively Enumerable Sets.
J. Symb. Log., 1993
Friedberg Splittings of Recursively Enumerable Sets.
Ann. Pure Appl. Log., 1993
Splitting Theorems in Recursion Theory.
Ann. Pure Appl. Logic, 1993
Every Recursive Boolean Algebra is Isomorphic to One with Incomplete Atoms.
Ann. Pure Appl. Log., 1993
Lattice Nonembeddings and Intervals of the Recursively Enumerable Degrees.
Ann. Pure Appl. Log., 1993
Countable Thin Pi<sup>0</sup><sub>1</sub> Classes.
Ann. Pure Appl. Log., 1993
Fixed-Parameter Intractability II (Extended Abstract).
Proceedings of the STACS 93, 1993
Parameterized Learning Complexity.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993
1992
Nondiamond Theorems for Polynomial Time Reducibility.
J. Comput. Syst. Sci., 1992
On co-Simple Isols and Their Intersection Types.
Ann. Pure Appl. Log., 1992
Tabular Degrees in alpha-Recursion Theory.
Ann. Pure Appl. Log., 1992
Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy.
Proceedings of the Complexity Theory: Current Research, 1992
Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992
Fixed-Parameter Intractability.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992
1991
On Computational Complexity and Honest Polynomial Degrees.
Theor. Comput. Sci., 1991
On Π<sub>1</sub><sup>0</sup> Classes and their Ranked Points.
Notre Dame J. Formal Log., 1991
Jumps of Hemimaximal Sets.
Math. Log. Q., 1991
1990
Lattice Nonembeddings and Initial Segments of the Recursively Enumerable Degrees.
Ann. Pure Appl. Log., 1990
Corrigendum: Correction to "Undecidability of L(F<sub>infty</sub>) and Other Lattices of r.e. Substructures".
Ann. Pure Appl. Log., 1990
Minimal Degrees Recursive in 1-Generic Degrees.
Ann. Pure Appl. Log., 1990
1989
On Choice Sets and Strongly Non-Trivial Self-Embeddings of Recursive Linear Orders.
Math. Log. Q., 1989
A Contiguous Nonbranching Degree.
Math. Log. Q., 1989
Recursively Enumerable m- and tt-Degrees. I: The Quantity of m- Degrees.
J. Symb. Log., 1989
Completely Mitotic r.e. Degrees.
Ann. Pure Appl. Log., 1989
Classification of Degree Classes Associated with r.e. Subspaces.
Ann. Pure Appl. Log., 1989
Intervals and Sublattices of the r.e. Weak Truth Table Degrees, Part II: Nonbounding.
Ann. Pure Appl. Log., 1989
Intervals and Sublattices of the r.e. Weak Truth Table Degrees, Part I: Density.
Ann. Pure Appl. Log., 1989
On Honest Polynomial Reductions, Relativizations, and P=NP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989
1988
Recursively enumerable <i>m</i>- and <i>tt</i>-degrees II: The distribution of singular degrees.
Arch. Math. Log., 1988
1987
Automorphisms and Recursive Structures.
Math. Log. Q., 1987
Ann. Pure Appl. Log., 1987
Localization of a theorem of Ambos-Spies and the strong anti-splitting property.
Arch. Math. Log., 1987
1986
Bases of Supermaximal Subspaces and Steinitz Systems II.
Math. Log. Q., 1986
Splitting Properties of R. E. Sets and Degrees.
J. Symb. Log., 1986
Structural interactions of the recursively enumerable T- and W-degrees.
Ann. Pure Appl. Log., 1986
Recursion theory and ordered groups.
Ann. Pure Appl. Log., 1986
Sound, totally sound, and unsound recursive equivalence types.
Ann. Pure Appl. Log., 1986
Undecidability of L(F<sub>∞</sub>) and other lattices of r.e. substructures.
Ann. Pure Appl. Log., 1986
1985
Effective Extensions of Linear Forms on a Recursive Vector Space Over a Recursive Field.
Math. Log. Q., 1985
Automorphisms of Supermaximal Subspaces.
J. Symb. Log., 1985
1984
A Note on Decompositions of Recursively Enumerable Subspaces.
Math. Log. Q., 1984
Some Remarks on a Theorem of Iraj Kalantari Concerning convexity and Recursion Theory.
Math. Log. Q., 1984
The Universal Complementation Property.
J. Symb. Log., 1984
Bases of Supermaximal Subspaces and Steinitz Systems. I.
J. Symb. Log., 1984
Co-Immune Subspaces and Complementation in V.
J. Symb. Log., 1984
Decidable Subspaces and Recursively Enumerable Subspaces.
J. Symb. Log., 1984
1983
On a Question of a. Retzlaff.
Math. Log. Q., 1983
