Andre Nies: publications

List of Publications from DBLP server of Uni Trier. (This site also provides citations in bibtex format. It only covers computer science and logic publications.) Many papers are also available on Research Gate or on arXiv.org.

My research is in 3 areas:

1. Computability, randomness, and their interactions with other fields (last updated July 2017).

2. Algebra, analysis, and effective presentations of structures (last updated July 2017).

3. Computability, degree structures, coding methods (last updated December 2013).

See here for papers in preparation and unpublished work.

Most of the research is supported by the Marsden fund of New Zealand. Current grant: Randomness, analysis, and reverse mathematics, 2014-18, with Noam Greenberg.

### 1. Computability, randomness, and interactions with other fields (68)

1. Muchnik degrees and cardinal characteristics. With Benoit Monin. Preprint. arXiv:1712.00864

2. Quantum Martin-Löf randomness. With Volkher Scholz. Preprint, arxiv.org/abs/1709.08422

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

4. Martin-Loef reducibility and cost functions. With Noam Greenberg, Joseph S. Miller, and Daniel Turetsky. Submitted July 2017.  arxiv.org/abs/1707.00258

5. Computing from projections of random points: a dense hierarchy of subideals of the K-trivial degrees. With Noam Greenberg and Joseph S. Miller. Submitted April 2018.  arxiv.org/abs/1707.00256

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

7. The reverse mathematics of theorems of Jordan and Lebesgue. With former Honors student Marcus Triplett, and Keita Yokoyama. Submitted April 2017.  arxiv.org/abs/1704.00931

8. Randomness and Differentiability. With V. Brattka and J. Miller. Transactions of the American Mathematical Society 368 (2016):581-605.

9. Martin-Loef randomness implies multiple recurrence in effectively closed sets. With R. Downey and S. Nandakumar. To appear in Notre Dame J. Formal Logic.

10. 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. Oberwolfach randomness, K-triviality, and differentiability.  Earlier preprint on the same topics, Mathematisches Forschungsinstitut Oberwolfach, 2012.

11. Research announcement: Computing K-trivial sets by incomplete random sets. With L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, and D. Turetsky. Bull. Symbolic Logic. 20, March 2014, pp 80-90.

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

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

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

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

16. A unifying approach to the Gamma question. With B. 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

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

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

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

20. Algorithmic aspects of Lipschitz functions. With C. Freer, B. Kjos-Hanssen and F. Stephan. Computability 3(1): 45-61 (2014).

21. 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.

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

23. Solovay functions and their applications in algorithmic randomness.  With L. Bienvenu, R. Downey, and W. 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.

24. Calculus of Cost Functions.  To appear in Barry Cooper and Mariya Soskova (eds.), THE INCOMPUTABLE - Journeys beyond the Turing barrier. Springer Verlag.

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

26. Characterizing the strongly jump-traceable sets via randomness. With N. Greenberg and D. Hirschfeldt. Advances in Mathematics 231 (2012), 2252-2293. Science Direct version. shorter version dated Oct. 2009.

27. 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.

28. The complexity of recursive splittings of random sets. With S. Ng and F. Stephan. Computability 3(1): 1-8 (2014).

29. Characterizing lowness for Demuth randomness.  With L. Bienvenu, R. Downey, N. Greenberg and D. Turetsky. J. Symbolic Logic 79 (2014), 526-560.

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

31. 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

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

33. Demuth's path to randomness (extended abstract).  With A. 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.

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

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

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

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

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

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

40. Counting the changes of random Delta_2 sets.  With S. Figueira, D. Hirschfeldt, J. Miller, and S. 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.

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

42. 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.

43. 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.

44. Higher Kurtz randomness.  With B. Kjos-Hanssen, F. Stephan, and L. Yu. Ann. Pure Appl. Logic 161 (2010), no. 10, 1280-1290.

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

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

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

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

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

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

51. 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.

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

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

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

55. 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.

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

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

58. 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.

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

60. 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

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

62. 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.

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

64. 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.

65. 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.

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

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

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

### 2. Algebra, analysis, and effective presentations of structures (24)

1. The complexity of topological group isomorphism. With Alexander S. Kechris and Katrin Tent. J. Symbolic Logic, in press.

2. 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.

3. The complexity of isomorphism between countably based profinite groups. Unpublished, arxiv.org/abs/1604.00609.

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

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

6. A universal separable diversity. With David Bryant and Paul Tupper. Analysis and Geometry in Metric Spaces, 2017.

7. 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.

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

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

10. Equivalence relations that are Sigma-3 complete for computable reducibility. With E. Fokina and S. 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.

11. Borel Structures: a brief survey. With A. 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.

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

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

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

15. Finite automata presentable abelian groups.  With P. 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.

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

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

18. 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),

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

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

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

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

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

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

### 3. Computability, degree structures, coding methods (35)

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 lattice 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.