Matthew Harrison-Trainor

Department of Mathematics, Statistics, and Computer Science
University of Illinois Chicago
Office: SEO 538
Email:

I am an Assistant Professor in the Department of Mathematics, Statistics, and Computer Science at the University of Illinois Chicago. My work is in logic and computability theory.

I am a member of the Mathematical Computer Science group.

My CV.

Slides from my tutorial at CiE2024: First Day | Second Day

profile photo

Papers

  1. Scott spectral gaps are bounded for linear orderings (with David Gonzalez)
    Submitted for publication. [ pdf ]

  2. On the computability of optimal Scott sentences (with Rachael Alvir and Barbara Csima)
    Submitted for publication. [ pdf ]

  3. A relation on \((\omega,<)\) of intermediate degree spectrum on a cone (with Jad Damaj)
    Submitted for publication. [ pdf ]

  4. Measuring the complexity of characterizing \([0,1]\), \(S^1\), and \(\mathbb{R}\) up to homeomorphism (with Eissa Haydar)
    Submitted for publication. [ pdf ]

  5. Back-and-forth equivalent group von Neumann algebras (with Isaac Goldbring)
    Submitted for publication. [ pdf ]

  6. Computable Gelfand duality (with Peter Burton, Christopher J. Eagle, Alec Fox, Isaac Goldbring, Timothy H. McNicholl, Alexander Melnikov, and Teerawat Thewmorakot)
    Submitted for publication. [ pdf ]

  7. An effective classification of Borel Wadge classes (with Adam Day, Noam Greenberg, and Dan Turetsky)
    Journal of the European Math Society, to appear. [ pdf ]

  8. Scott analysis, linear orders, and almost periodic functions (with David Gonzalez and Meng-Che "Turbo" Ho)
    Bulletin of the London Mathematical Society, to appear. [ pdf ]

  9. Coding information into all infinite subsets of a dense set (with Lu Liu and Patrick Lutz)
    Israel Journal of Mathematics, to appear. [ pdf ]

  10. Two results on complexities of decision problems of groups (with Uri Andrews and Meng-Che "Turbo" Ho)
    International Journal of Algebra and Computation, 35 (2025), no. 2, 311–327. [ pdf ]

  11. The logic of cardinality comparison without the axiom of choice (with Dhruv Kulshreshtha)
    Annals of Pure and Applied Logic, 175 (2025), no. 4, 103549, 22 pp. [ pdf ]

  12. Enumerations of families closed under finite differences (with Noam Greenberg, Joe Miller, and Dan Turetsky)
    Computability, 13 (2024), no. 1, 89–104. [ pdf ]

  13. Infinitary logic has no expressive efficiency over finitary logic (with Miles Kretschmer)
    Journal of Symbolic Logic, 89 (2024), no. 4, 1817 1834. [ pdf ]

  14. An arithmetic analysis of closed surfaces (with Alexander Melnikov)
    Transactions of the AMS, 377 (2024), 1543 1596. [ pdf ]

  15. Iterated priority arguments in descriptive set theory (with Adam Day, Noam Greenberg, and Dan Turetsky)
    Bulletin of Symbolic Logic, 30 (2024), no. 2, 199 226. [ pdf ]

  16. Computable Stone spaces (with Nikolay Bazhenov and Alexander Melnikov)
    Annals of Pure and Applied Logic, 174 (2023), no. 9, 103304, 25 pp. [ pdf | DOI ]

  17. A minimal set low for speed (with Rod Downey)
    Journal of Symbolic Logic, 87 (2022), no. 4, 1693–1728. [ pdf | DOI ]

  18. An analysis of random elections with large numbers of voters
    Mathematical Social Sciences, 116 (2022), 68–84. [ pdf | DOI ]

  19. Which classes of structures are both pseudo-elementary and \(\mathcal{L}_{\omega_1 \omega}\)-elementary? (with Will Boney, Barbara Csima and Nancy Day)
    Bulletin of Symbolic Logic, 29 (2022), no. 1, 1–18. [ pdf | DOI ]

  20. An introduction to the Scott complexity of countable structures and a survey of recent results
    Bulletin of Symbolic Logic, 28 (2022), no. 1, 71–103. [ pdf | DOI ]

  21. Relationships between computability-theoretic properties of problems (with Rod Downey, Noam Greenberg, Ludovic Patey, and Dan Turetsky)
    Journal of Symbolic Logic, 87 (2022), no. 1, 47–71. [ pdf | DOI ]

  22. The tree of tuples of a structure (with Antonio Montalbán)
    Journal of Symbolic Logic, 87 (2022), no. 1, 21–46. [ pdf | DOI ]

  23. Scott complexity of countable structures (with Rachael Alvir, Noam Greenberg, and Dan Turetsky)
    Journal of Symbolic Logic, 86 (2021), no. 4, 1706–1720. [ pdf | DOI ]

  24. Some questions of uniformity in algorithmic randomness (with Laurent Bienvenu and Barbara Csima)
    Journal of Symbolic Logic, 86 (2021), no. 4, 1612–1631. [ pdf ]

  25. Computing sets from all infinite subsets (with Noam Greenberg, Ludovic Patey, and Dan Turetsky)
    Transactions of the AMS, 374 (2021), 8131–8160. [ pdf | DOI ]

  26. Non-density in punctual computability (with Noam Greenberg, Alexander Melnikov, and Dan Turetsky)
    Annals of Pure and Applied Logic, 172 (2021), no. 9, 102985, 17 pp. [ pdf | DOI ]

  27. Relativizing computable categoricity (with Rod Downey and Alexander Melnikov)
    Proceedings of the AMS, 149 (2021), no. 9, 3999–4013. [ pdf | DOI ]

  28. The property “arithmetic-is-recursive” on a cone (with Uri Andrews and Noah Schweber)
    Journal of Mathematical Logic, 21 (2021), no. 3, 2150021. [ pdf | DOI ]

  29. Finitely generated groups are universal among finitely generated structures (with Meng-Che "Turbo" Ho)
    Annals of Pure and Applied Logic, 172 (2021), no. 1, 102855, 21 pp. [ pdf | DOI ]

  30. Computability up to homeomorphism (with Alexander Melnikov and Keng Meng Ng)
    Journal of Symbolic Logic, 85 (2020), no. 4, 1664–1686. [ pdf | DOI ]

  31. The logic of comparative cardinality (with Yifeng Ding and Wesley Holliday)
    Journal of Symbolic Logic, 85 (2020), no. 3, 972–1005. [ pdf | DOI ]

  32. Graphs are not universal for online computability (with Rod Downey, Iskander Kalimullin, Alexander Melnikov, and Daniel Turetsky)
    Journal of Computing and Systems Sciences, 112 (2020), 1–12. [ pdf | DOI ]

  33. Degrees of categoricity above limit ordinals (with Barbara Csima, Michael Deveau, and Mohammad Assem Mahmoud)
    Computability, 9 (2020), no. 2, 127–137. [ pdf | DOI ]

  34. Optimal bounds for single-source Kolmogorov extractors (with Laurent Bienvenu and Barbara Csima)
    Transactions of the AMS, 373 (2020), no. 3, 1983–2006. [ pdf | DOI ]

  35. First-order possibility models and finitary completeness proofs
    Review of Symbolic Logic, 12 (2019), no. 4, 637–662. [ pdf | DOI ]

  36. Automatic and polynomial-time algebraic structures (with Nikolay Bazhenov, Iskander Kalimullin, Alexander Melnikov, and Keng Meng Ng)
    Journal of Symbolic Logic, 84 (2019), no. 4, 1630–1669. [ pdf | DOI ]

  37. Constructing decidable graphs from decidable structures (with Nikolay Bazhenov)
    Algebra and Logic, 58 (2019), no. 5, 369–382. [ pdf | DOI ]

  38. Characterizations of cancellable groups (with Meng-che Ho)
    Proceedings of the AMS, 147 (2019), no. 8, 3533–3545. [ pdf | DOI ]

  39. Effective aspects of algorithmically random structures (with Bakh Khoussainov and Daniel Turetsky)
    Computability, 8 (2019), no. 3-4, 359–375. [ pdf | DOI ]

  40. A first-order theory of Ulm type
    Computability, 8 (2019), no. 3-4, 347–358. [ pdf | DOI ]

  41. There is no classification of the decidably presentable structures
    Journal of Mathematical Logic, 18 (2018), no. 2. [ pdf | DOI ]

  42. Borel functors and infinitary interpretations (with Russell Miller and Antonio Montalbán).
    Journal of Symbolic Logic, 83 (2018), no. 4, 1434–1456. [ pdf | DOI ]

  43. On optimal Scott sentences of finitely generated algebraic structures (with Meng-Che "Turbo" Ho)
    Proceedings of the AMS, 146 (2018), no. 10, 4473–4485. [ pdf | DOI ]

  44. Degree spectra of relations on a cone
    Memoirs of the AMS, 253 (2018), no. 1208. [ pdf | DOI ]

  45. Computable valued fields
    Archive for Mathematical Logic, 57 (2018), no. 5–6, 473–495. [ pdf | DOI ]

  46. Some new computable structures of high rank (with Gregory Igusa and Julia Knight).
    Proceedings of the AMS, 146 (2018), no. 7, 3097–3109. [ pdf | DOI ]

  47. Scott ranks of models of a theory
    Advances in Mathematics, 330 (2018), 109–147. [ pdf | DOI ]

  48. Left-orderable computable groups
    Journal of Symbolic Logic, 83 (2018), no. 1, 237–255. [ pdf | DOI ]

  49. Inferring probability comparisons (with Wesley Holliday and Thomas Icard)
    Mathematic Social Science, 91 (2018), 62–70. [ pdf | DOI ]

  50. On computable field embeddings and difference closed fields (with Alexander Melnikov and Russell Miller).
    Canadian Journal of Mathematics, 69 (2017), no. 6, 1338–1363. [ pdf | DOI ]

  51. The Gamma question for many-one degrees
    Annals of Pure and Applied Logic, 168 (2017), no. 7, 1396–1405. [ pdf | DOI ]

  52. Preferential structures for comparative probabilistic reasoning (with Wesley Holliday and Thomas Icard).
    AAAI, (2017), 1135–1141. [ pdf | DOI ]

  53. Computable functors and effective interpretability (with Alexander Melnikov, Russell Miller, and Antonio Montalbán).
    Journal of Symbolic Logic, 82 (2017), no. 1, 77–97. [ pdf | DOI ]

  54. Degrees of categoricity on a cone via \(\eta\)-systems (with Barbara Csima)
    Journal of Symbolic Logic, 82 (2017), no. 1, 325–346. [ pdf | DOI ]

  55. A note on cancellation axioms for comparative probability (with Wesley Holliday and Thomas Icard)
    Theory and Decision, 80 (2016), no. 1, 159–166. [ pdf | DOI ]

  56. Independence in computable algebra (with Alexander Melnikov and Antonio Montalbán).
    Journal of Algebra, 443 (2015), 441–468. [ pdf | DOI ]

  57. Differential-algebraic jet spaces preserve internality to the constants (with Zoé Chatzidakis and Rahim Moosa).
    Journal of Symbolic Logic, 80 (2015), no. 3, 1022–1034. [ pdf | DOI ]

  58. Nonstandard methods for bounds in differential polynomial rings (with Rahim Moosa and Jack Klys).
    Journal of Algebra, 360 (2012), 71–86. [ pdf | DOI ]