Professor, Department of Mathematics
University of Wisconsin–Madison

Office: 521 Van Vleck
Email: ude.csiw.htam@rellimj
480 Lincoln Drive
Madison, WI 53706
This is a picture of me looking at a waterfall in NZ. It was taken by Noam Greenberg in 2007. It's one of my favorite pictures of myself, but I should replace it before the difference from my actual age becomes too embarrassing.

Biography

I received my Ph.D. in Mathematics from Cornell University in August of 2002 under the direction of Anil Nerode. At the same time, I was awarded a Masters Degree in Computer Science. I took a three year VIGRE Postdoctoral fellowship in the Mathematics Department of Indiana University in Bloomington, although I spent one of those years visiting Rod Downey at Victoria University in Wellington. After three years in a tenure-track position at the University of Connecticut, I moved to the University of Wisconsin—Madison in the Fall of 2008.
June 11, 2017

    Submitted

  1. Complexity profiles and generic Muchnik reducibility (with Uri Andrews, Noah Schweber, and Mariya I. Soskova). Submitted.  [PDF]

    2. Accepted

  2. Maximal towers and ultrafilter bases in computability theory (with Steffen Lempp, André Nies, and Mariya I. Soskova). To appear in the Journal of Symbolic Logic.  [PDF]  [DOI]
  3. PA relative to an enumeration oracle (with Jun Le Goh, Iskander Kalimulin, and Mariya I. Soskova). To appear in the Journal of Symbolic Logic.  [PDF]  [DOI]
  4. Expanding the reals by continuous functions adds no computational power (with Uri Andrews, Julia F. Knight, Rutger Kuyper, and Mariya I. Soskova). To appear in the Journal of Symbolic Logic.  [PDF]
  5. Enumerations of families closed under finite differences (with Noam Greenberg, Matthew Harrison-Trainor, and Daniel Turetsky). To appear in Computability.  [PDF]
  6. Martin-Löf reducibility and cost functions (with Noam Greenberg, André Nies, and Daniel Turetsky). To appear in the Israel Journal of Mathematics.  [PDF]
  7. Cuts in the ML degrees (with Katherine Arthur and Noam Greenberg). To appear in Aspects of Computation, IMS Lecture Notes Series.  [PDF]

    8. Published

  8. A structural dichotomy in the enumeration degrees (with Hristo A. Ganchev, Iskander Sh. Kalimullin, and Mariya I. Soskova). Journal of Symbolic Logic, 87(2):527–544, 2022.  [PDF]  [DOI]
  9. Computability and the symmetric difference operator (Uri Andrews, Peter Gerdes, Steffen Lempp, and Noah Schweber). Logic Journal of the IGPL, 30(3):499–518, 2022.  [PDF]  [DOI]
  10. Highness properties close to PA completeness (with Noam Greenberg and André Nies). Israel Journal of Mathematics, 244(1):419–465, 2021.  [PDF]  [DOI]
  11. Computing from projections of random points (with Noam Greenberg and André Nies). Journal of Mathematical Logic, 20(1):1950014, 41 pp., 2020.  [PDF]  [DOI]
  12. Chaitin's $\Omega$ as a continuous function (with Rupert Hölzl, Wolfgang Merkle, Frank Stephan, and Liang Yu). Journal of Symbolic Logic, 85(1):486–510, 2020.  [PDF]  [DOI]
    13. The almost total degrees and the continuous degrees coincide. We thought that was too nice to be true, but it's true!
  13. Characterizing the continuous degrees (with Uri Andrews, Gregory Igusa, and Mariya I. Soskova). Israel Journal of Mathematics, 234(2):743–767, 2019.  [PDF]  [DOI]
  14. On cototality and the skip operator in the enumeration degrees (with Uri Andrews, Hristo A. Ganchev, Rutger Kuyper, Steffen Lempp, Alexandra A. Soskova, and Mariya I. Soskova). Transactions of the American Mathematical Society, 372(3):1631–1670, 2019.  [PDF]  [DOI]
  15. Connected choice and the Brouwer fixed point theorem (with Vasco Brattka, Stéphane Le Roux, and Arno Pauly). Journal of Mathematical Logic, 19(1):1950004, 46 pp., 2019.  [PDF]  [DOI]
    Preliminary version: The Brouwer fixed point theorem revisited. Pursuit of the Universal: CiE 2016, volume 9709 of Lecture Notes in Computer Science, pages 58–67. Springer, 2016.  [DOI]
  16. Energy randomness (with Jason Rute). Israel Journal of Mathematics, 227(1):1–26, 2018.  [PDF]  [DOI]
  17. Two more characterizations of K-triviality (with Noam Greenberg, Benoit Monin, and Daniel Turetsky). Notre Dame Journal of Formal Logic, 59(2):189–195, 2018.  [PDF]  [DOI]
  18. Density of the cototal enumeration degrees (with Mariya I. Soskova). Annals of Pure and Applied Logic, 169(5):450–462, 2018.  [PDF]  [DOI]
  19. Dimension 1 sequences are close to randoms (with Noam Greenberg, Alexander Shen, and Linda Brown Westrick). Theoretical Computer Science, 705:99–112, 2018.  [PDF]  [DOI]
  20. Forcing with bushy trees (with Mushfeq Khan). Bulletin of Symbolic Logic, 23(2):160–180, 2017.  [PDF]  [DOI]
  21. Theory spectra and classes of theories (with Uri Andrews, Mingzhong Cai, David Diamondstone, and Steffen Lempp). Transactions of the American Mathematical Society, 369(9):6493–6510, 2017.  [PDF]  [DOI]
  22. Nullifying randomness and genericity using symmetric difference (with Rutger Kuyper). Annals of Pure and Applied Logic, 168(9):1692–1699, 2017.  [PDF]  [DOI]
  23. On work of Barmpalias and Lewis-Pye: A derivation on the d.c.e. reals. Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, volume 10010 of Lecture Notes in Computer Science, pages 644–659. Springer, 2017.  [PDF]  [DOI]
  24. On Kalimullin pairs (with Mingzhong Cai, Steffen Lempp, and Mariya I. Soskova). Computability, 5(2):111–126, 2016.  [PDF]  [DOI]
  25. The complements of lower cones of degrees and the degree spectra of structures (with Uri Andrews, Mingzhong Cai, Iskander Sh. Kalimullin, Steffen Lempp, and Antonio Montalbán). Journal of Symbolic Logic, 81(3):997–1006, 2016.  [PDF]  [DOI]
  26. Generic Muchnik reducibility and presentations of fields (with Noam Greenberg and Rod Downey). Israel Journal of Mathematics, 216(1):371–387, 2016.  [PDF]  [DOI]
  27. Defining totality in the enumeration degrees (with Mingzhong Cai, Hristo Ganchev, Steffen Lempp, and Mariya I. Soskova). Journal of the American Mathematical Society, 29(4):1051–1067, 2016.  [PDF]  [DOI]
  28. Randomness and differentiability (with Vasco Brattka and André Nies). Transactions of the American Mathematical Society, 368(1):581–605, 2016.  [Radio Edit]  [Uncensored Album Version]  [DOI]
  29. Counting the changes of random $\Delta^0_2$ sets (with Santiago Figueira, Denis Hirschfeldt, Keng Meng Ng, and André Nies). Journal of Logic and Computation, 25(4):1073–1089, 2015.  [PDF]  [DOI]
    Preliminary version in Proceedings of CiE 2010, volume 6158 of Lecture Notes in Computer Science, pages 162–171. Springer, 2010.  [PDF]  [DOI]
  30. On the structure of the degrees of relative provability (with Uri Andrews, Mingzhong Cai, David Diamondstone, and Steffen Lempp). Israel Journal of Mathematics, 207(4):449–478, 2015.  [PDF]  [DOI]
  31. Density, forcing, and the covering problem (with Adam Day). Mathematical Research Letters, 22(3):719–727, 2015.  [PDF]  [DOI]
  32. Spectra of theories and structures (with Uri Andrews). Proceedings of the American Mathematical Society, 143(3):1283–1298, 2015.  [PDF]  [DOI]
  33. Lowness for effective Hausdorff dimension (with Steffen Lempp, Keng Meng Ng, Daniel Turetsky, and Rebecca Weber). Journal of Mathematical Logic, 14(2):1450011, 22 pp., 2014.  [PDF]  [DOI]
  34. Random strings and tt-degrees of Turing complete c.e. sets (with Mingzhong Cai, Rod Downey, Rachel Epstein, and Steffen Lempp). Logical Methods in Computer Science, 10(3):15, 24 pp., 2014.  [PDF]  [DOI]
  35. Computing K-trivial sets by incomplete random sets (with Laurent Bienvenu, Adam Day, Noam Greenberg, Antonín Kučera, André Nies, and Daniel Turetsky). Bulletin of Symbolic Logic, 20(1):80–90, 2014.  [PDF]  [DOI]
  36. Universal computably enumerable equivalence relations (with Uri Andrews, Steffen Lempp, Keng Meng Ng, Luca San Mauro, and Andrea Sorbi). Journal of Symbolic Logic, 79(1):60–88, 2014.  [PDF]  [DOI]
  37. Cupping with random sets (with Adam Day). Proceedings of the American Mathematical Society, 142(8):2871–2879, 2014.  [PDF]  [DOI]
  38. Denjoy, Demuth, and density (with Laurent Bienvenu, Rupert Hölzl, and André Nies). Journal of Mathematical Logic, 14(1):1450004, 35 pp., 2014.  [PDF]  [DOI]
    Preliminary version: The Denjoy alternative for computable functions. Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of Leibniz International Proceedings in Informatics, pages 543–554. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.  [PDF]  [DOI]
    39. Hidden in this paper: you can compute a 2-generic given sufficient escape power, but not a weak 3-generic.
  39. The degrees of bi-hyperhyperimmune sets (with Uri Andrews and Peter Gerdes). Annals of Pure and Applied Logic, 165(3):803–811, 2014.  [PDF]  [DOI]
  40. Joining non-low c.e. sets with diagonally non-computable functions (with Laurent Bienvenu, Noam Greenberg, Antonín Kučera, André Nies, and Daniel Turetsky). Journal of Logic and Computation, 23(6):1183–1194, 2013.  [PDF]  [DOI]
  41. Randomness for non-computable measures (with Adam Day). Transactions of the American Mathematical Society, 365(7):3575–3591, 2013.  [PDF]  [DOI]
  42. Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets (with Johanna Franklin, Noam Greenberg, and Keng Meng Ng). Proceedings of the American Mathematical Society, 140(10):3623–3628, 2012.  [PDF]  [DOI]
  43. Lowness notions, measure and domination (with Bjørn Kjos-Hanssen and Reed Solomon). Journal of the London Mathematical Society. Second Series, 85(3):869–888, 2012.  [PDF]  [DOI]
  44. Randomness notions and partial relativization (with George Barmpalias and André Nies). Israel Journal of Mathematics, 191(2): 791–816, 2012.  [PDF]  [DOI]
  45. Randomness and lowness notions via open covers (with Laurent Bienvenu). Annals of Pure and Applied Logic, 163(5): 506–518, 2012.  [PDF]  [DOI]
  46. Two notes on subshifts. Proceedings of the American Mathematical Society, 140(5):1617–1622, 2012.  [PDF]  [DOI]
  47. Diagonally non-recursive functions and effective Hausdorff dimension (with Noam Greenberg). Bulletin of the London Mathematical Society, 43(4):636–654, 2011.  [PDF]  [DOI]
  48. Oscillation in the initial segment complexity of random reals (with Liang Yu). Advances in Mathematics, 226(6):4816–4840, 2011.  [PDF]  [DOI]
  49. Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. Advances in Mathematics, 226(1):373–384, 2011.  [PDF]  [DOI]
  50. The $K$-degrees, low for $K$ degrees, and weakly low for $K$ sets. Notre Dame Journal of Formal Logic, 50(4):381–391, 2009.  [PDF]  [DOI]
  51. Degree spectra of unary relations on $\langle\omega,\leq\rangle$ (with Rod Downey, Bakhadyr Khoussainov, and Liang Yu). In Logic, Methodology and Philosophy of Science: Proceedings of the Thirteenth International Congress, pages 36–55. College Publications, 2009.  [PDF]
  52. Indifferent sets (with Santiago Figueira and André Nies). Journal of Logic and Computation, 19(2):425–443, 2009.  [PDF]  [DOI]
  53. Lowness for Kurtz randomness (with Noam Greenberg). Journal of Symbolic Logic, 74(2):665–678, 2009.  [PDF]  [DOI]
  54. The upward closure of a perfect thin class (with Rod Downey and Noam Greenberg). Annals of Pure and Applied Logic, 156(1):51–58, 2008.  [PDF]  [DOI]
  55. Prompt simplicity, array computability and cupping (with Rod Downey, Noam Greenberg, and Rebecca Weber). In Computational prospects of infinity. Part II: Presented talks, volume 15 of Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, pages 59–77. World Scientific, 2008.  [PDF]  [DOI]
  56. On initial segment complexity and degrees of randomness (with Liang Yu). Transactions of the American Mathematical Society, 360(6):3193–3210, 2008.  [PDF]  [DOI]
  57. Randomness and halting probabilities (with Verónica Becher, Santiago Figueira, and Serge Grigorieff). Journal of Symbolic Logic, 71(4):1411–1430, 2006.  [PDF]  [DOI]
  58. Every 1-generic computes a properly 1-generic (with Barbara Csima, Rod Downey, Noam Greenberg, and Denis Hirschfeldt). Journal of Symbolic Logic, 71(4):1385–1393, 2006.  [PDF]  [DOI]
  59. Uniform almost everywhere domination (with Peter Cholak and Noam Greenberg). Journal of Symbolic Logic, 71(3):1057–1072, 2006.  [PDF]  [DOI]
  60. Randomness and computability: open questions (with André Nies). Bulletin of Symbolic Logic, 12(3):390–410, 2006.  [PDF]  [DOI]  (André Nies has an updated version on his webpage.)
  61. On self-embeddings of computable linear orderings (with Rod Downey and Carl Jockusch). Annals of Pure and Applied Logic, 138(1-3):52–76, 2006.  [PDF]  [DOI]
  62. Kolmogorov–Loveland randomness and stochasticity (with Wolfgang Merkle, André Nies, Jan Reimann, and Frank Stephan). Annals of Pure and Applied Logic, 138(1-3):183–210, 2006.  [PDF]  [DOI]
    Preliminary version in Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), volume 3404 of Lecture Notes in Computer Science, pages 422–433. Springer, 2005.  [PDF]  [DOI]
  63. A basis theorem for $\Pi^0_1$ classes of positive measure and jump inversion for random reals (with Rod Downey). Proceedings of the American Mathematical Society, 134(1):283–288, 2006.  [PDF]  [DOI]
  64. Relativizing Chaitin's halting probability (with Rod Downey, Denis Hirschfeldt, and André Nies). Journal of Mathematical Logic, 5(2):167–192, 2005.  [PDF]  [DOI]
  65. The undecidability of iterated modal relativization (with Lawrence S. Moss). Studia Logica, 79(3):373–407, 2005.  [PDF]  [DOI]
  66. Every 2-random real is Kolmogorov random. Journal of Symbolic Logic, 69(3):907–913, 2004.  [PDF]  [DOI]
    67. This is probably my best paper. I guess that I peaked early.
  67. Degrees of unsolvability of continuous functions. Journal of Symbolic Logic, 69(2):555–584, 2004.  [PDF]  [DOI]
  68. Effectiveness for infinite variable words and the Dual Ramsey Theorem (with Reed Solomon). Archive for Mathematical Logic, 43(4):543–555, 2004.  [PDF]  [DOI]
  69. $\Pi^0_1$ classes in computable analysis and topology. Ph.D. dissertation, Cornell University, 2002.  [Abstract]
  70. Effectiveness for embedded spheres and balls. In CCA 2002: Fifth Workshop on Computability and Complexity in Analysis, volume 66(1) of Electronic Notes in Theoretical Computer Science, pages 127–138. Elsevier, 2002.  [PDF]  [DOI]
  71. Decidability and complexity results for timed automata and semi-linear hybrid automata. In Hybrid Systems: Computation and Control, volume 1790 of Lecture Notes in Computer Science, pages 296–309. Springer, 2000.  [PDF]  [DOI]

    72. Expository paper

  72. Randomness, computability and information. In H. Zenil, editor, Randomness through Computation, World Scientific, 2011.  [PDF]  [DOI]

Research note

August 28, 2022

Coauthors

Word clouds are a pretty silly way to present data, and full names are too long for it to work well. But whatever, I like it anyway.
Implemented using wordcloud2.js
This list is too long and it's missing too many of my colleagues.

Assorted Colleagues

    June 16, 2019

    $\Pi^0_1$ classes in computable analysis and topology

    by Joseph S. Miller
    Ph.D. dissertation, Cornell University, 2002.
    Available upon request.
    Abstract. We explore aspects of $\Pi^0_1$ classes in $\mathbb{R}^n$. These are the effective closed sets of computable analysis and natural analogs of the $\Pi^0_1$ classes in $2^\omega$, widely studied by computability theorists. In Chapter II, we characterize the fixable classes—the sets of fixed point of computable maps from the unit cube $[0,1]^n$ to itself—as the $\Pi^0_1$ classes which contain a nonempty, connected $\Pi^0_1$ subclass. This settles a question asked in Cenzer and Jockusch (2000). To prove that Brouwer's theorem is inconsistent with Russian constructivism, Orevkov gave a fixable class with no computable points (1963). Our proof employs a generalization of Orevkov's construction, as well as the notion of topological degree. Homology theory is used in the definition and computation of the topological degree. Homology returns in Chapter III, where chains are used to take algorithmic advantage of the topological structure of a $\Pi^0_1$ class. We show that a $\Pi^0_1$ class homeomorphic to a sphere is located: the distance to the class is computable. Closed balls embedded as $\Pi^0_1$ classes are also studied. Chapter IV studies members of $\Pi^0_1$ classes which contain no computable points. These avoidable points were introduced by Kalantari and Welch. Avoidability is a type of effective non-computability; we introduce hyperavoidability, a stronger notion, and initiate the computability theoretic study of both classes, including their behavior in the Turing and weak truth-table degrees.
    June 11, 2017