Andre Nies: publications

Google Scholar homepage

Top publications


Criteria: citations, venue, or impact in some other form. Reverse chronological order.

  1. Computable topological abelian groups.
    With Martino Lupini and Alexander Melnikov. Journal of Algebra 615 (2023): 278-327.

  2. Finite axiomatizability for profinite groups.
    With Dan Segal and Katrin Tent. Proceedings of the London Math. Society, Volume 123, Issue 6, Dec 2021, Pages 597-635.

  3. Computing from projections of random points: a dense hierarchy of subideals of the K-trivial degrees.
    With Noam Greenberg and Joseph S. Miller. Journal of Mathematical Logic 20, no. 01 (2020), 1950014.  Arxiv version

  4. Metric Scott analysis.
    With I. Ben Yaacov, M. Doucha and T. Tsankov. Advances in Mathematics 318 (2017) 46–87.

  5. Coherent randomness tests and computing the K-trivial sets. 
    With L. Bienvenu, N. Greenberg, A. Kucera, and D. Turetsky. J. European Math. Society 18 (2016), 773-812. Kalman Prize for best paper by the NZMS, 2018.

  6. Randomness and Differentiability.
    With V. Brattka and J. Miller. Transactions of the American Mathematical Society 368 (2016):581-605.   Covered in the last chapter of the 2022 book Landscape of 21st Century Mathematics by Bogdan Grechuk.

  7. A unifying approach to the Gamma question.
    With B. Monin. 30th Annual {ACM/IEEE} Symposium on Logic in Computer Science (LICS) 2015, Kyoto, 585-596. Version on conference site.
    Journal paper Muchnik degrees and cardinal characteristics. With B. Monin. The Journal of Symbolic Logic 86.2 (2021): 471-498.

  8. Characterizing the strongly jump-traceable sets via randomness.
    With N. Greenberg and D. Hirschfeldt. Advances in Mathematics 231 (2012), 2252-2293.

  9. Interactions of computability and randomness.
    Proceedings of the International Congress of Mathematicians (S. Ragunathan, ed.) 30-57 (2010).

  10. Computability and Randomness. Oxford University Press, 2009, 452 pages. Paperback version 2011. New edition in progress (2022).

  11. Randomness via effective descriptive set theory.  
    With G. Hjorth. J. London Math Soc 75 (2), 2007: 495-508.

  12. Automatic Structures: Richness and Limitations. 
    With B. Khoussainov, S. Rubin and F. Stephan. Logic in Computer Science (LICS) 04, Helsinki.
    Journal version in Log. Methods Comput. Sci. 3 (2007), no. 2, 2:2, 18 pages (electronic),

  13. Describing Groups. 
    Bull. Symb. Logic. 13 no 3 (2007), 305-339.

  14. Randomness, relativization and Turing degrees. 
    With F. Stephan and S. Terwijn. J. Symb. Logic 70(2), 515-535 (2005).

  15. Lowness properties and randomness. 
    Advances in Mathematics 197, Issue 1 (2005), 274-305.

  16. Separating classes of groups by first order sentences. 
    Intern. J.  of Algebra and Computation 13, No 3 (2003), 287-302.

  17. Aspects of free groups.  
    J. Algebra 263 (2003), 119-125.

  18. Randomness, computability and density. 
    With R. Downey and D. Hirschfeldt. Siam J. Computing 31 (2002), 1169-1183 (extended abstract in Proc. STACS  2001). 

  19. Intervals of the lattice of computably enumerable sets and effective boolean algebras.
    Bull. Lond. Math. Society. 29 (1997) 683-692.

  20. Interpretability and definability in the Recursively Enumerable Degrees.
    With R. Shore and T. Slaman. Proc. London Math. Soc. (3) 77 (1998), 241-291.

  21. Coding in the partial order of enumerable sets.
    With L. Harrington. Advances in Mathematics 133 (1998), 133-162.


My research is in several areas:


1. Group theory, descriptive set theory, and effective presentations of structures.

2. Computability, randomness, and their interactions with other fields.

3. Computability, degree structures, coding methods.

Most of the research has been supported by the Marsden fund of New Zealand.


1. Group theory, descriptive set theory, and effective presentations of structures



  1. Oligomorphic groups, their automorphism groups, and the complexity of their isomorphism.
    With Gianluca Paolini. Submitted.

  2. Automorphism groups of non-Archimedean groups.
    With Philipp Schlicht. In prep.

  3. Computably locally compact groups and their closed subgroups.
    With Alexander Melnikov. Accepted for publication in IJAC.

  4. Fractal dimensions and profinite groups.
    With Elvira Mayordomo. Submitted.

  5. Word automatic groups of nilpotency class 2.
    With Frank Stephan. Information Processing Letters 183 (2024): 106426.

  6. Computably totally disconnected locally compact groups.
    With Alexander Melnikov. Preprint, 2024. Submitted.

  7. Finite axiomatizability for profinite groups.
    With Dan Segal and Katrin Tent. Proceedings of the London Math. Society, Volume 123, Issue 6, Dec 2021, Pages 597-635.

  8. Computable topological abelian groups.
    With Martino Lupini and Alexander Melnikov. Journal of Algebra 615 (2023): 278-327.

  9. Coarse groups, and the isomorphism problem for oligomorphic groups.
    With Philipp Schlicht and Katrin Tent. J. Math Logic (2021): 2150029.

  10. Fraïssé limits for relational metric structures.
    With David Bryant and Paul Tupper. J. Symb. Logic 86.3 (2021): 913-934. 

  11. Effectively closed subgroups of the infinite symmetric group.
    With Noam Greenberg, Alexander Melnikov, and Dan Turetsky. Proceedings of the American Mathematical Society 146.12 (2018): 5421-5435.

  12. The complexity of topological group isomorphism.
    With Alexander S. Kechris and Katrin Tent. The Journal of Symbolic Logic 83.3 (2018): 1190-1203.

  13. Metric Scott analysis.
    With Itai Ben Yaacov, Michal Doucha and Todor Tsankov. Advances in Mathematics 318 (2017) 46–87. Note: this replaces "A Lopez-Escobar theorem for continuous logic" posted on arXiv in 2014.

  14. Describing finite groups by short first-order sentences.
    With Katrin Tent. Israel J. Mathematics 221 (2017), 85–115.

  15. The complexity of isomorphism between countably based profinite groups.
    Unpublished (2016), last section included in paper with Kechris and Tent, arxiv.org/pdf/1604.00609.

  16. Scott analysis of Polish spaces.
    With Sy Friedman, Ekaterina Fokina, and Martin Koerwien. Unpublished work dating from 2012.  

  17. Calibrating word problems of groups via the complexity of equivalence relations.
    With Andrea Sorbi. Mathematical Structures in Computer Science 1-15, 2016.

  18. A universal separable diversity.
    With David Bryant and Paul Tupper. Analysis and Geometry in Metric Spaces, 2017.
    (Note minor erratum added on last page.) Journal page.

  19. Local compactness for computable Polish metric spaces is $\Pi^1_1$-complete.
    With Slawomir Solecki. In A. Beckmann et al. (Eds.): CiE 2015, LNCS 9136, 286–290, 2015.

  20. The Classification Problem for Compact Computable Metric Spaces.
    With Alexander G. Melnikov. CiE 2013: 320-328.

  21. Universality for left-computably enumerable metric spaces.
    With Alexander Gavruskin. Lobachevskii Journal of Mathematics 35.4 (2014): 292-294.

  22. Equivalence relations that are Sigma-3 complete for computable reducibility.
    With Ekaterina Fokina and Sy Friedman. In Luke Ong and Ruy de Queiroz (editors), Logic, Language, Information and Computation, Proceedings of Wollic 2012, Buenos Aires, 26-34. LNCS 7456, Springer.

  23. Borel Structures: a brief survey.
    With Antonio Montalban. Effective Mathematics of the Uncountable, Noam Greenberg, Joel David Hamkins, Denis Hirschfeldt, and Russell Miller, eds., Lecture Notes in Logic 41 (2013), 124-134.

  24. Borel Structures and Borel Theories.
    With Greg Hjorth. J. Symb. Logic 76 (2011), 461-476.

  25. From Automatic Structures to Borel Structures.
    With Greg Hjorth, Bakhadyr Khoussainov, and Antonio Montalban. Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS) 2008, 431-441.

  26. Describing Groups. 
    Bull. Symb. Logic. 13 no 3 (2007), 305-339.

  27. Finite automata presentable abelian groups. 
    With Pavel Semukhin. Proc. of Logical Foundations of Computer Science (LFCS) 2007, LNCS 4514, 422-436. Journal version in Annals of Pure and Applied Logic, 161:458-467, 2009.

  28. FA-presentable groups and rings. 
    With Rick Thomas. J. Algebra 320 (2008), 569-585.

  29. Comparing quasi-finitely axiomatizable and prime groups.
    J. Group Theory 10 (2007), 347-361.

  30. Automatic Structures: Richness and Limitations. 
    With Bakhadyr Khoussainov, Sasha Rubin and Frank Stephan. Logic in Computer Science (LICS) 04, Helsinki.
    Journal version in Log. Methods Comput. Sci. 3 (2007), no. 2, 2:2, 18 pages (electronic),

  31. Finitely generated groups and first-order logic.
    With Andrej Morozov. J. London Math. Society (2) 71 (2005) 542-562.

  32. Separating classes of groups by first order sentences.
    Intern. J. of Algebra and Computation 13, No 3 (2003), 287-302.

  33. Aspects of free groups.
    J. Algebra 263 (2003), 119-125.

  34. A new spectrum of recursive models .  
    Notre Dame J. Formal Logic  40  (1999),  no. 3, 307-314.

  35. Recursive Models of Theories with Few Models.
    With Bakhadyr Khoussainov and Richard Shore. Notre Dame Journal of Formal Logic (2) 38 (1997), 165-178.

  36. Interpreting infinite linear orders.
    With Wilfrid Hodges. Logic Colloquium '95, J.A. Makowsky and E.V. Ravve (Hrsg.), Lecture Notes in Logic 11 (1998), 73-78, Springer Verlag.



2. Computability, randomness, and interactions with other fields



  1. Martin-Loef reducibility and cost functions. With Noam Greenberg, Joseph S. Miller, and Daniel Turetsky. Israel Journal of Mathematics 260.1 (2024): 261-301. 

  2. Immunity, Diagonalization and the Complexity of Mass Problems. With Achilles Beros, Mushfeq Khan and Bjorn Kjos-Hanssen. In Aspects of computation and automata theory with application, World Scientific, 2023 (pp. 115-139).

  3. Maximal Towers and Ultrafilter Bases in Computability Theory.
    With Steffen Lempp, Joseph S. Miller, and Mariya Soskova. J. Symb. Logic, 2022, pp 1-20.  

  4. Randomness and initial segment complexity for probability measures.
    With Frank Stephan. STACS 2020, 12 pages. Journal version Theoretical Computer Science 900 (2022): 1-19.  

  5. Highness properties close to PA completeness.
    With Noam Greenberg and Joseph S. Miller. Israel J. of Mathematics, 1-47 (2021).  

  6. Martin-Löf random quantum states.
    With Volkher Scholz. Journal of Mathematical Physics 60, 092201 (2019). Journal page.   arXiv.

  7. Computing from projections of random points: a dense hierarchy of subideals of the K-trivial degrees.
    With Noam Greenberg and Joseph S. Miller. Journal of Mathematical Logic 20, no. 01 (2020), 1950014.  Arxiv version

  8. Muchnik degrees and cardinal characteristics.
    With Benoit Monin. The Journal of Symbolic Logic 86.2 (2021): 471-498.  

  9. Randomness notions and reverse mathematics.
    With Paul Shafer. The Journal of Symbolic Logic, 85(1):271-299, doi:10.1017/jsl.2019.50. arXiv: 1808.02746  

  10. Closure of resource bounded randomness notions under polynomial time permutations.
    With Frank Stephan. STACS 2018, 51, 1-51:10.  

  11. Randomness and Solovay degrees.
    With Kenshi Miyabe and Frank Stephan.   J. Logic & Analysis 10 (2018)

  12. The reverse mathematics of theorems of Jordan and Lebesgue.
    With former Honors student Marcus Triplett, and Keita Yokoyama. The Journal of Symbolic Logic 86.4 (2021): 1657-1675.  arxiv.org/pdf/1704.00931

  13. Calculus of Cost Functions. 
    In Barry Cooper and Mariya Soskova (eds.), THE INCOMPUTABLE - Journeys beyond the Turing barrier, 183-216. Springer Verlag, 2017.

  14. Randomness and Differentiability.
    With Vasco Brattka and Joseph S. Miller. Transactions of the American Mathematical Society 368 (2016):581-605.  

  15. Martin-Loef randomness implies multiple recurrence in effectively closed sets.
    With Rod Downey and Satyadev Nandakumar. Notre Dame Journal of Formal Logic 60.3 (2019): 491-502.

  16. Coherent randomness tests and computing the K-trivial sets. 
    With Laurent Bienvenu, Noam Greenberg, Antonin Kucera, and Dan Turetsky. J. European Math. Society 18 (2016), 773-812. Kalman Prize for best paper by the NZMS, 2018. Oberwolfach randomness, K-triviality, and differentiability.  Earlier preprint on the same topics, Mathematisches Forschungsinstitut Oberwolfach, 2012.

  17. Research announcement: Computing K-trivial sets by incomplete random sets.
    With Laurent Bienvenu, Adam Day, Noam Greenberg, Antonin Kucera, Josehp Miller, and Dan Turetsky. Bull. Symbolic Logic. 20, March 2014, pp 80-90.

  18. Lowness, Randomness, and computable analysis. 
    Lecture Notes in Computer Science 10010:738-754, Jan 2017.

  19. Lightface Pi-0-3-completeness of density sets under effective Wadge reducibility.
    With Gemma Carotenuto. In: 12th Conference on Computability in Europe (CiE), Paris, Beckmann A, Bienvenu L. (eds.) Lecture Notes in Computer Science 9709: 234-239.

  20. Using almost-everywhere theorems from analysis to study randomness.
    With Kenshi Miyabe and Jing Zhang. Bulletin of Symbolic Logic 22(3):305-331, 2016.

  21. A computational approach to the Borwein-Ditor Theorem.
    With Alexander Galicki. In: 12th Conference on Computability in Europe (CiE), Paris, Beckmann A., Bienvenu L. (eds.) Lecture Notes in Computer Science 9709: 99-104

  22. A unifying approach to the Gamma question.
    With Benoit Monin. 30th Annual {ACM/IEEE} Symposium on Logic in Computer Science (LICS), 2015, Kyoto, Japan, July 6-10, 2015, 585-596. http://dx.doi.org/10.1109/LICS.2015.60

  23. Differentiability of polynomial time computable functions.
    In E. W. Mayr and N. Portier (Eds.), Proceedings of 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), LIPIcs, Vol. 25, 602-613.

  24. Denjoy, Demuth, and Density. 
    With Laurent Bienvenu, Rupert Hoelzl, and Joseph Miller. Much extended journal version of a STACS 2012 paper with the same authors. J. Math. Logic 14 (2014), 1450004 (35 pages).

  25. Demuth's path to randomness.
    With Cristopher Porter and Antonin Kucera. Bull. Sym. Logic 21(3):270-305 01 Sep 2015.

  26. Algorithmic aspects of Lipschitz functions.
    With Cameron Freer, Bjorn Kjos-Hanssen and Frank Stephan. Computability 3(1): 45-61 (2014).

  27. Joining non-low C.E. sets with diagonally non-computable functions.
    With Laurent Bienvenu, Noam Greenberg, Antonin Kucera, Joseph S. Miller, and Dan Turetsky. J. Logic Computation (2013) 23 (6): 1183-1194.

  28. An analogy between cardinal characteristics and highness properties of oracles.
    With Joerg Brendle, Andrew Brooke-Taylor and Keng Meng Ng. In Proc. Asian Logic Colloquium 2013, World Scientific (2015).

  29. Solovay functions and their applications in algorithmic randomness. 
    With Laurent Bienvenu, Rod Downey, and Wolfgang Merkle. J. Computer System Sciences, Volume 81, Issue 8, December 2015, Pages 1575–1591. Note: published version has typo in the abstract. Download the pdf file for the correct version.

  30. Feasible analysis, randomness, and base invariance.
    With Santiago Figueira. Theory Comput. Syst. 56(3): 439-464 (2015).

  31. Calibrating the complexity of Delta-2 sets via their changes. 
    In J. Brendle, R. Downey, R. Goldblatt, B. Kim (eds.), Proceedings of the 12th Asian Logic Conference 2011, World Scientific (2013), 285-297. ArXiv.

  32. The complexity of recursive splittings of random sets.
    With Keng Meng Ng and Frank Stephan. Computability 3(1): 1-8 (2014).

  33. Characterizing lowness for Demuth randomness.
    With Laurent Bienvenu, Rod Downey, Noam Greenberg and Dan Turetsky. J. Symbolic Logic 79 (2014), 526-560.

  34. The Denjoy alternative for computable functions.
    With Laurent Bienvenu, Rupert Hoelzl, and Joseph Miller. STACS 2012, 543-554 (version with unpublished appendix containing proofs; full Journal version has appeared in J. Math Logic, 2014).

  35. Computably enumerable sets below random sets.
    Annals of Pure and Applied Logic 163 (2012), pp. 1596-1610. DOI: 10.1016/j.apal.2011.12.011

  36. Characterizing the strongly jump-traceable sets via randomness.
    With Noam Greenberg and Denis Hirschfeldt. Advances in Mathematics 231 (2012), 2252-2293. Science Direct version. Shorter version dated Oct. 2009.

  37. Randomness notions and partial relativization.
    With George Barmpalias and Joseph S. Miller. Israel Journal of Mathematics 191(2):791-816, Sept 2012. DOI: 10.1007/s11856-012-0012-5.

  38. Demuth's path to randomness (extended abstract).
    With Antonin Kucera. Computation, Physics and Beyond. Lecture Notes in Computer Science, 2012, Volume 7160/2012, 159-173, DOI: 10.1007/978-3-642-27654-5_12.

  39. K-triviality in computable metric spaces.
    With Alexander Melnikov. Proc. Amer. Math. Soc. 141 (2013), no. 8, 2885-2899.

  40. Benign cost functions and lowness properties.
    With Noam Greenberg. J. Symb. Logic 76, Issue 1 (2011), 289-312. DOI: 10.2178/jsl/1294171001.

  41. Low upper bounds in the Turing degrees revisited.
    With George Barmpalias. J. Log. Comput. 22(4): 693-699 (2012).

  42. Demuth randomness and computational complexity.
    With Antonin Kucera. Annals of Pure and Applied Logic 162 (2011) 504-513.

  43. Solovay functions and K-triviality.
    With Laurent Bienvenu and Wolfgang Merkle. 28th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2011), Dortmund, Germany - LIPIcs 9, pages 452-463.

  44. Interactions of computability and randomness.
    Proceedings of the International Congress of Mathematicians (S. Ragunathan, ed.) 30-57 (2010).

  45. Counting the changes of random Delta_2 sets.
    With Santiago Figueira, Denis Hirschfeldt, Joseph S. Miller, and Selwyn Ng. Journal version of a paper submitted to CiE 2010, Azores, Portugal, J Logic Computation (2015) 25 (4): 1073-1089 doi:10.1093/logcom/exs083.

  46. Upper bounds on ideals in the computably enumerable Turing degrees.
    With George Barmpalias. Ann. Pure Applied Logic 162 (6) 465-473. DOI: 10.1016/j.apal.2010.12.005.

  47. Studying randomness through computation.
    A (mostly) non-technical discussion of the development of the area within the last 8 years. In: H.Zenil, editor, Randomness through computation, World Scientific (2011), 207-223.

  48. Superhighness and strong jump traceability.
    In: Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, Wolfgang Thomas (eds.): Automata, Languages and Programming, 36th International Colloquium, ICALP 2009 Lecture Notes in Computer Science 5555, 726-737.

  49. Higher Kurtz randomness.
    With Bjorn Kjos-Hanssen, Frank Stephan, and Liang Yu. Ann. Pure Appl. Logic 161 (2010), no. 10, 1280-1290.

  50. Indifferent sets.
    With Santiago Figueira and Joseph S. Miller. J. Logic and Computation 19 (2009), no 2, 425-443.

  51. Superhighness.
    With Bjorn Kjos-Hanssen. Notre Dame J. Formal Logic, 50 (2009), 445-452.

  52. Universal recursively enumerable sets of strings.
    With Cristian Calude, Ludwig Staiger, and Frank Stephan. Theoretical Computer Science 412 (22), 2253-2261. Conference version in Twelfth International Conference DLT 2008, Kyoto, Proceedings. Springer LNCS 5257:170-182, 2010.

  53. Lowness for higher randomness.
    With Chitat Chong and Liang Yu. Israel J. Math 166 (2008), No 1, 39-60.

  54. Eliminating concepts.
    In Computational prospects of infinity II, Volume 15 of IMS Lecture Notes Series, 2008, pp 225-248. World Scientific.

  55. Lowness for Computable Machines.
    With Rod Downey, Noam Greenberg and Nenad Mikhailovich). In Computational prospects of infinity II, Volume 15 of IMS Lecture Notes Series, 2008, pp. 79-86. World Scientific.

  56. A lower cone in the wtt degrees of non-integral effective dimension.
    With Jan Reimann. In Computational prospects of infinity II, Volume 15 of IMS Lecture Notes Series, 2008, pp. 249-260. World Scientific.

  57. Non-cupping and randomness.
    Proc. Amer. Math. Soc. 135 (2007), no. 3, 837--844.

  58. Lowness and $\Pi_2^0$ Nullsets.
    With Rod Downey, Rebecca Weber, and Liang Yu. Journal of Symbolic logic 71( 3), 2006, pp. 1044-1052.

  59. Randomness via effective descriptive set theory.   With Greg Hjorth. J. London Math Soc 75 (2), 2007: 495-508.

  60. Calibrating randomness.  With R. Downey, D. Hirschfeldt and S. Terwijn. Bull. Symb. Logic. 12 no 3 (2006) 411-491   Received the 2010 Shoenfield prize of the ASL for best survey paper.

  61. Randomness and computability: Open questions.  With J. S. Miller. Bull. Symb. Logic. 12 no 3 (2006) 390-410.

  62. Lowness properties and randomness.  Advances in Mathematics 197, Issue 1 (2005), 274-305.

  63. Using random sets as oracles.  With D. Hirschfeldt and F. Stephan. Journal of the London Mathematical Society 75 (2007) 610 - 622. 18th most cited article on their Jan 1, 2013 list.

  64. Lowness properties and approximations of the jump.  With S. Figueira and F. Stephan. Ann. Pure Applied Logic 152 (2008), 51-66.

  65. Kolmogorov-Loveland randomness and Stochasticity. With Wolfgang Merkle, Joe Miller, Jan Reimann and Frank Stephan. STACS 2005 version.
    Full version,  Ann. Pure Applied Logic 138 (2006), 183-210

  66. Relativizing Chaitin's halting probability.  With Rod Downey, Denis Hirschfeldt and Joe Miller. J. Math. Logic, Vol. 5, No. 2 (2005) 167-192.

  67. Lowness for the class of Schnorr random sets.  With B. Kjos-Hanssen and F. Stephan. SIAM J. Comput. 35 (2005), no. 3, 647--657. Preliminary results in: Lowness properties of reals and hyper-immunity.  With B. Bedregal. Proceedings of Wollic 2003, Electronic Notes in Theoretical Computer Science 84, Elsevier.

  68. Randomness, relativization and Turing degrees.  With F. Stephan and S. Terwijn. J. Symb. Logic 70(2), 515-535 (2005).

  69. Program Size Complexity for Possibly Infinite Computations.  With V. Becher, S. Figueira and S. Picchi. Notre Dame Journ. Formal Logic vol 46,l no 1 (2005), 51-64.

  70. Reals which compute little.  Proceedings of Logic Colloquium 2002, Chatzidakis, Z, Koepke, P. and Pohlers, W., editors, Lecture Notes in Logic 27 (2002), 261-275.

  71. Trivial reals.  With R. Downey, D. Hirschfeldt and F. Stephan. Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press, 103-131. 

  72. Randomness, computability and density.  With R. Downey and D. Hirschfeldt. Siam J. Computing 31 (2002), 1169-1183 (extended abstract in Proc. STACS  2001). 

  73. Chaitin Omega Numbers and Strong Reducibilities. With C. Calude. J. Univ. Comp. Sc. 3 (1998), 1162-1166.


3. Computability, degree structures, coding methods


  1. Complexity of equivalence relations and preorders from computability theory.  With E. Ianovski, Russell Miller, Keng Meng Ng. Journal of Symbolic Logic 79, September 2014, 859 - 881.

  2. The first order theories of the Medvedev and Muchnik lattices.  With A. Lewis and A. Sorbi. CiE 2009 Proceedings, 324-331.

  3. Parameter definability in the r.e. degrees.  J. Math. Logic 3, no 1 (2003), 37-65.

  4. The AE-Theory of $R, \leq,v,\wedge)$ is Undecidable   With R. Miller and R. Shore. Trans. Amer. Math. Soc. vol. 356 (2004), no. 8, pp. 3025-3067.

  5. Global properties of the lattice of $\Pi^0_1$-classes. With D. Cenzer. Proceedings of the AMS 132 (1) 239-249.

  6. Global properties of degree structures. In the Scope of Logic, Methodology and Philosophy of Science, P. Gardenfors e.a. (eds), Vol I, 65-80.

  7. Initial segments of the lattice of $\Pi^0_1$ classes. With D. Cenzer. J. Symb. Logic, 66 (2001), 1749--1765.

  8. Effectively dense Boolean algebras and their applications. Trans. Amer. Math. Soc. 352, no.  11 (2000), 4989-5012.

  9. Branching in the Sigma-2 enumeration degrees. With A. Sorbi. Israel J.  Math. 110 (1999), 29-59

  10. Structural properties and $\Sigma^0_2$ enumeration degrees. With A. Sorbi. J. Symb. Logic. 65 no. 1 (2000), 285-293.

  11. Interpreting the natural numbers in the computably enumerable weak truth table degrees.  Ann. Pure Appl. Logic 107 (2001), no. 1-3, 35-48.

  12. On the filter of c.e. supersets of an r-maximal set. With S. Lempp and R. Solomon. Math. Log. Q. 46 (2000), no. 4, 555-561.

  13. Model theory of the computably enumerable many­-one degrees. Logic Journal of the IGPL 8 (1999), issue 5.

  14. Coding Methods in Computability Theory and Complexity Theory. Habilitation thesis, January 1998, 106 pages.

  15. Differences of c.e. sets. With S. Lempp. Math. Logic Quarterly 46 (2000), 555-561.

  16. Lattices of supersets of r-maximal sets. With P. Cholak. Israel J. of Math., 113 (1999), 305-322.

  17. Enumerable sets and quasireducibility. R. Downey and G. LaForte. Annals of Pure and Applied Logic 95 (1998), pp. 1-35.

  18. Undecidability results for low--level degree structures. Extended abstract (5 pages). With R. Downey. Proceedings of the twelfth IEEE Conference on Computational Complexity (1997), 128-132. Full version in Journal of Computer and System Sciences 60 (2000).

  19. Intervals of the lattice of computably enumerable sets and effective boolean algebras. Bull. Lond. Math. Society. 29 (1997) 683-692.

  20. Interpretability and definability in the Recursively Enumerable Degrees. With R. Shore and T. Slaman. Proc. London Math. Soc. (3) 77 (1998), 241-291.

  21. Definability in the recursively enumerable Turing-degrees. With R. Shore and T. Slaman. Bull. Symbolic Logic (4) 2 (1996), 392-403.

  22. Coding in the partial order of enumerable sets. With L. Harrington. Advances in Mathematics 133 (1998), 133-162.

  23. The Pi3-theory of the enumerable Turing degrees is undecidable. With S. Lempp and T. Slaman. Trans.\ Amer.\ Math.\ Soc.\ (7) 350 (1998), 2719-2736.

  24. Relativizations of structures arising from recursion theory . In: S. B. Cooper e.a. (Eds.) Computability, enumerability, unsolvability. London Math. Soc. Lecture Notes Series 224, Cambridge University Press, 219-232.

  25. On a uniformity in degree structures. In: Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, Feb. 1997, 261-276.

  26. Undecidability of the 4-quantifier theory for the recursively enumerable Turing­ and wtt­ degrees. With S. Lempp. Journal of Symbolic Logic 60 (1995), No 4, 1118--1136

  27. The last question on recursively enumerable many­-one degrees. Algebra i Logika 33(5), 1995, 550-563. Translation July 1995.

  28. Undecidable fragments of elementary theories. Algebra Universalis, 35 (1996) 8-33.

  29. Interpreting true arithmetic in the theory of the recursively enumerable truth table degrees . With R. Shore. Annals of Pure and Applied Logic (3) 75 (1995), 269-311.

  30. Recursively enumerable equivalence relations modulo finite differences. Mathematical Logic Quarterly 40(1994), 490-518.

  31. Interpreting true arithmetic in degree structures. Kurt G\"odel Kolloquium 1993, Lecture Notes in Computer Science 713, 255-263.

  32. Cappable recursively enumerable degrees and Posts program. With K. Ambos-Spies. Archive of Math. Logic (1992) 32, 51-56.

  33. The theory of the polynomial many-one degrees of recursive sets is undecidable. With K. Ambos-Spies. STACS 92, Lecture Notes in Computer Science 577, 209-210.

  34. Definability and Undecidability in Recursion Theoretic Semilattices. Ph. D. Thesis, Universitaet Heidelberg, 1992.

  35. The theory of the recursively enumerable weak truth-table degrees is undecidable. With K. Ambos-Spies and R. Shore. Journal of Symbolic Logic, 57(1992), no. 3, 864-874.