Joseph S. Miller
Professor
Office: 521 Van Vleck
Email: ude.csiw.htam@rellimj
Fax: (608) 263-8891
University of Wisconsin–Madison
Department of Mathematics
480 Lincoln Drive
Madison, WI 53706
Research papers
  1. Dimension 1 sequences are close to randoms (with Noam Greenberg, Alexander Shen, and Linda Brown Westrick). Submitted.  [PDF]

  2. 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). Submitted.  [PDF]

  3. Connected choice and the Brouwer fixed point theorem (with Vasco Brattka, Stéphane Le Roux, and Arno Pauly). Submitted.  [PDF]

  4. Computing from projections of random points: a dense hierarchy of subideals of the $K$-trivial degrees (with Noam Greenberg and André Nies). Submitted.  [PDF]

  5. Energy randomness (with Jason Rute). Submitted.  [PDF]

  6. Nullifying randomness and genericity using symmetric difference (with Rutger Kuyper). To appear in the Annals of Pure and Applied Logic.  [PDF]

  7. On work of Barmpalias and Lewis-Pye: A derivation on the d.c.e. reals. To appear in Proceedings of the International Symposium on Computability and Complexity (in honour of Rod Downey's 60th birthday), Lecture Notes in Computer Science, Springer.  [PDF]

  8. Generic Muchnik reducibility and presentations of fields (with Noam Greenberg and Rod Downey). To appear in the Israel Journal of Mathematics.  [PDF]

  9. Theory spectra and classes of theories (with Uri Andrews, Mingzhong Cai, David Diamondstone, and Steffen Lempp). To appear in the Transactions of the American Mathematical Society.  [PDF]

  10. On Kalimullin pairs (with Mingzhong Cai, Steffen Lempp, and Mariya Soskova). To appear in Computability.  [PDF]

  11. 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). To appear in the Journal of Symbolic Logic.  [PDF]

  12. Two more characterizations of K-triviality (with Noam Greenberg, Benoit Monin, and Daniel Turetsky). To appear in the Notre Dame Journal of Formal Logic.  [PDF]

  13. Defining totality in the enumeration degrees (with Mingzhong Cai, Hristo Ganchev, Steffen Lempp, and Mariya Soskova). Journal of the American Mathematical Society, 29(4):1051–1067, 2016.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  14. 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][BibTeX] — [zbMATH][MathSciNet][Scopus]

  15. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

    Preliminary version in Proceedings of CiE 2010, volume 6158 of Lecture Notes in Computer Science, pages 162–171. Springer, 2010.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  16. 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][BibTeX] — [zbMATH][MathSciNet][Scopus]

  17. Density, forcing, and the covering problem (with Adam Day). Mathematical Research Letters, 22(3):719–727, 2015.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  18. Spectra of theories and structures (with Uri Andrews). Proceedings of the American Mathematical Society, 143(3):1283–1298, 2015.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  19. Lowness for effective Hausdorff dimension (with Steffen Lempp, Keng Meng Ng, Dan Turetsky, and Rebecca Weber). Journal of Mathematical Logic, 14(2):1450011, 22 pp., 2014.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  20. 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][BibTeX] — [zbMATH][MathSciNet][dblp]

  21. Computing K-trivial sets by incomplete random sets (with Laurent Bienvenu, Adam Day, Noam Greenberg, Antonín Kučera, André Nies, and Dan Turetsky). Bulletin of Symbolic Logic, 20(1):80–90, 2014.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  22. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  23. Cupping with random sets (with Adam Day). Proceedings of the American Mathematical Society, 142(8):2871–2879, 2014.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  24. 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][BibTeX] — [zbMATH][MathSciNet][Scopus]

    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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  25. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  26. Joining non-low c.e. sets with diagonally non-computable functions (with Laurent Bienvenu, Noam Greenberg, Antonín Kučera, André Nies, and Dan Turetsky). Journal of Logic and Computation, 23(6):1183–1194, 2013.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  27. Randomness for non-computable measures (with Adam Day). Transactions of the American Mathematical Society, 365(7):3575–3591, 2013.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  28. 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][BibTeX] — [zbMATH][MathSciNet][Scopus]

  29. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  30. Randomness notions and partial relativization (with George Barmpalias and André Nies). Israel Journal of Mathematics, 191(2): 791–816, 2012.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  31. Randomness and lowness notions via open covers (with Laurent Bienvenu). Annals of Pure and Applied Logic, 163(5): 506–518, 2012.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  32. Two notes on subshifts. Proceedings of the American Mathematical Society, 140(5):1617–1622, 2012.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  33. Diagonally non-recursive functions and effective Hausdorff dimension (with Noam Greenberg). Bulletin of the London Mathematical Society, 43(4):636–654, 2011.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  34. Oscillation in the initial segment complexity of random reals (with Liang Yu). Advances in Mathematics, 226(6):4816–4840, 2011.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  35. Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. Advances in Mathematics, 226(1):373–384, 2011.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  36. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  37. 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 35–55. College Publications, 2009.  [PDF]

  38. Indifferent sets (with Santiago Figueira and André Nies). Journal of Logic and Computation, 19(2):425–443, 2009.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  39. Lowness for Kurtz randomness (with Noam Greenberg). Journal of Symbolic Logic, 74(2):665–678, 2009.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  40. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  41. 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][BibTeX] — [zbMATH][MathSciNet]

  42. On initial segment complexity and degrees of randomness (with Liang Yu). Transactions of the American Mathematical Society, 360(6):3193–3210, 2008.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][Scopus]

  43. Randomness and halting probabilities (with Verónica Becher, Santiago Figueira, and Serge Grigorieff). Journal of Symbolic Logic, 71(4):1411–1430, 2006.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  44. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  45. Uniform almost everywhere domination (with Peter Cholak and Noam Greenberg). Journal of Symbolic Logic, 71(3):1057–1072, 2006.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  46. Randomness and computability: open questions (with André Nies). Bulletin of Symbolic Logic, 12(3):390–410, 2006.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]
    (André Nies has an updated version on his webpage.)

  47. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  48. 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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

    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][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  49. 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][BibTeX] — [zbMATH][MathSciNet][Scopus]

  50. Relativizing Chaitin's halting probability (with Rod Downey, Denis Hirschfeldt, and André Nies). Journal of Mathematical Logic, 5(2):167–192, 2005.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet]

  51. The undecidability of iterated modal relativization (with Lawrence S. Moss). Studia Logica, 79(3):373–407, 2005.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  52. Every 2-random real is Kolmogorov random. Journal of Symbolic Logic, 69(3):907–913, 2004.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  53. Degrees of unsolvability of continuous functions. Journal of Symbolic Logic, 69(2):555–584, 2004.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  54. Effectiveness for infinite variable words and the Dual Ramsey Theorem (with Reed Solomon). Archive for Mathematical Logic, 43(4):543–555, 2004.
    [PDF][DOI][BibTeX] — [zbMATH][MathSciNet][dblp][Scopus]

  55. $\Pi^0_1$ classes in computable analysis and topology. Ph.D. dissertation, Cornell University, 2002.
    [HTML] — [MathSciNet]

  56. 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][BibTeX] — [zbMATH][dblp][Scopus]

  57. 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][BibTeX] — [zbMATH][dblp][Scopus]

Expository paper(s)
  • Randomness, computability and information. In H. Zenil, editor, Randomness through Computation, World Scientific, 2011.
    [PDF][DOI][BibTeX] — [zbMATH][Scopus]
Research note(s)
  • Contrasting plain and prefix-free Kolmogorov complexity. Download pdf.

Slides from selected talk(s)
  • Extracting randomness is hard. Logic Colloquium 2008, Bern, Switzerland, July 6, 2008. Download pdf.

  • Randomness and computational computability-theoretic strength. Joint Mathematics Meetings, San Francisco, CA, January 15, 2010. Download pdf.

Giving a lecture
On top of Niesen, in Switzerland. For the record, I ascended by funicular, not foot.
Giving a lecture
In front of the Fajing (formally Daming) temple pagoda in Yangzhou, China.

March 01, 2017