Matthew Harrison-TrainorContactUniversity of Michigan.Office: 3836 East Hall. Email: Curriculum VitaeMy CV. My research statement.About MeI am currently a Donald J. Lewis Research Assistant Professor at the University of Michigan. Previously I was a post-doctoral fellow working with Rod Downey at Victoria University of Wellington and Alexander Melnikov at Massey University. Before that I was a Banting post-doctoral fellow at the University of Waterloo working with Barbara Csima. My main interests are in computability theory, and in particular, computable structure theory. I have also published work on model theory and differential algebra, modal logic, and probability theory. I received my PhD under the supervision of Antonio Montalbán at the University of California, Berkeley. My thesis, The Complexity of Countable Structures, received the Sacks Prize from the Association for Symbolic Logic for the most outstanding thesis in mathematical logic worldwide and the Herb Alexander Prize for the most outstanding thesis in mathematics at UC Berkeley. |
Iterated priority arguments in descriptive set theory (with Adam Day, Noam Greenberg, and Dan Turetsky)
Submitted for publication. [ pdf ]
An effective classification of Borel Wadge classes (with Adam Day, Noam Greenberg, and Dan Turetsky)
Submitted for publication. [ pdf ]
Infinitary logic has no expressive efficiency over finitary logic (with Miles Kretschmer)
Submitted for publication. [ pdf ]
An arithmetical characterization of closed surfaces (with Alexander Melnikov)
Submitted for publication. [ pdf ]
Computable Stone spaces (with Nikolay Bazhenov and Alexander Melnikov)
Submitted for publication. [ pdf ]
Enumerations of families closed under finite differences (with Noam Greenberg, Joe Miller, and Dan Turetsky)
Submitted for publication. [ pdf ]
There is no simple characterization of the relatively decidable theories
Submitted for publication. [ pdf ]
Describing finitely presented algebraic structures
Submitted for publication. [ pdf ]
A representation theorem for possibility models
Submitted for publication. [ pdf ]
A minimal set low for speed (with Rod Downey)
Journal of Symbolic Logic, to appear. [ pdf ]
An analysis of random elections with large numbers of voters
Mathematical Social Sciences, to appear. [ pdf ]
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, to appear. [ pdf ]
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 ]
Some questions of uniformity in algorithmic randomness (with Laurent Bienvenu and Barbara Csima)
Journal of Symbolic Logic, 86 (2021), no. 4, 1612–1631. [ pdf ]
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 ]
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 ]
The tree of tuples of a structure (with Antonio Montalbán)
Journal of Symbolic Logic, 87 (2022), no. 1, 21–46. [ pdf | DOI ]
Computing sets from all infinite subsets (with Noam Greenberg, Ludovic Patey, and Dan Turetsky)
Transactions of the AMS, 374 (2021), 8131–8160. [ pdf | DOI ]
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 ]
Relativizing computable categoricity (with Rod Downey and Alexander Melnikov)
Proceedings of the AMS, 149 (2021), no. 9, 3999–4013. [ pdf | DOI ]
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 ]
Computability up to homeomorphism (with Alexander Melnikov and Keng Meng Ng)
Journal of Symbolic Logic, 85 (2020), no. 4, 1664–1686. [ pdf | DOI ]
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 ]
The logic of comparative cardinality (with Yifeng Ding and Wesley Holliday)
Journal of Symbolic Logic, 85 (2020), no. 3, 972–1005. [ pdf | DOI ]
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 ]
Degrees of categoricity above limit ordinals (with Barbara Csima, Michael Deveau, and Mohammad Assem Mahmoud)
Computability, 9 (2020), no. 2, 127–137. [ pdf | DOI ]
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 ]
First-order possibility models and finitary completeness proofs
Review of Symbolic Logic, 12 (2019), no. 4, 637–662. [ pdf | DOI ]
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 ]
Constructing decidable graphs from decidable structures (with Nikolay Bazhenov)
Algebra and Logic, 58 (2019), no. 5, 369–382. [ pdf | DOI ]
Characterizations of cancellable groups (with Meng-che Ho)
Proceedings of the AMS, 147 (2019), no. 8, 3533–3545. [ pdf | DOI ]
Effective aspects of algorithmically random structures (with Bakh Khoussainov and Daniel Turetsky)
Computability, 8 (2019), no. 3-4, 359–375. [ pdf | DOI ]
A first-order theory of Ulm type
Computability, 8 (2019), no. 3-4, 347–358. [ pdf | DOI ]
There is no classification of the decidably presentable structures
Journal of Mathematical Logic, 18 (2018), no. 2. [ pdf | DOI ]
Borel functors and infinitary interpretations (with Russell Miller and Antonio Montalbán).
Journal of Symbolic Logic, 83 (2018), no. 4, 1434–1456. [ pdf | DOI ]
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 ]
Degree spectra of relations on a cone
Memoirs of the AMS, 253 (2018), no. 1208. [ pdf | DOI ]
Computable valued fields
Archive for Mathematical Logic, 57 (2018), no. 5–6, 473–495. [ pdf | DOI ]
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 ]
Scott ranks of models of a theory
Advances in Mathematics, 330 (2018), 109–147. [ pdf | DOI ]
Left-orderable computable groups
Journal of Symbolic Logic, 83 (2018), no. 1, 237–255. [ pdf | DOI ]
Inferring probability comparisons (with Wesley Holliday and Thomas Icard)
Mathematic Social Science, 91 (2018), 62–70. [ pdf | DOI ]
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 ]
The Gamma question for many-one degrees
Annals of Pure and Applied Logic, 168 (2017), no. 7, 1396–1405. [ pdf | DOI ]
Preferential structures for comparative probabilistic reasoning (with Wesley Holliday and Thomas Icard).
AAAI, (2017), 1135–1141. [ pdf | DOI ]
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 ]
Degrees of categoricity on a cone via \(\eta\)-systems (with Barbara Csima)
Journal of Symbolic Logic, 82 (2017), no. 1, 325–346. [ pdf | DOI ]
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 ]
Independence in computable algebra (with Alexander Melnikov and Antonio Montalbán).
Journal of Algebra, 443 (2015), 441–468. [ pdf | DOI ]
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 ]
Nonstandard methods for bounds in differential polynomial rings (with Rahim Moosa and Jack Klys).
Journal of Algebra, 360 (2012), 71–86. [ pdf | DOI ]
The tree of tuples of a structure.
Joint Mathematics Meeting Special Session on Computability Theory and Effective Mathematics. January 2021
Scott complexity of countable structures.
Berkeley Logic Colloquium. October 2020
Analysing the complexity of characterization and classification problems. (video)
The First Workshop at the Mathematical Center in Akademgorodok. July 2020
The tree of tuples of a structure. (video)
Computability Theory and Applications Online Seminar. May 2020
Introreducibility.
Berkeley Computability Seminar, Berkeley, CA. October 2019.
Introreducibility.
University of Waterloo Logic Seminar, Waterloo, Canada. October 2019.
Describing countable structures. (slides)
Logic Colloquium, Prague, Czech Republic. August 2019.
The complexity of classifications and descriptions. (slides)
Maltsev Meeting, Novosibirsk, Russia. August 2018.
There is no natural construction of a structure of Scott rank \(\omega_1^{CK}\).
University of Wisconsin-Madison Logic Seminar, Madison, WI. March 2018.
When is a property expressed in infinitary logic also pseudo-elementary?
Oberwolfach, Germany. January 2018.
When is a property expressed in infinitary logic also pseudo-elementary? (slides)
Notre Dame Logic Seminar, South Bend, IN. November 2017.
Scott ranks of computable structures. (slides)
New England Recursion and Definability Seminar, Wellesley, MA. October 2017.
Some computable structure theory of finitely generated structures. (slides)
Mid-Atlantic Mathematical Logic Seminar, New York, NY. October 2017.
Some computable structure theory of finitely generated structures.
Scott ranks of computable structures.
Cornell Logic Seminar, Ithaca, NY. October 2017.
Some computable structure theory of finitely generated structures. (slides)
Aspects of Computation, Singapore. May 2017.
Describing finitely generated structures.
UCLA Logic Seminar, Los Angeles, CA. May 2017.
Optimal Scott sentences for finitely generated groups.
AMS Spring Central Sectional Meeting, Bloomington, IN. April 2017.
There is no classification of the decidably presentable structures.
University of Wisconsin-Madison Logic Seminar, Madison, WI. March 2017.
Some results on characterizing structures using infinitary formulas. (slides)
ASL North American Annual Meeting, Boise, ID. March 2017.
Extending automorphisms of normal algebraic fields. (slides)
AMS Spring Southeastern Sectional Meeting, Charleston, SC. March 2017.
Optimal Scott sentences for finitely generated groups.
Southeastern Logic Symposium, Gainesville, FL. March 2017.
Computable structures of high Scott rank. (slides)
Workshop on Computability, Ghent, Belgium. July 2016.
Borel functors and interpretations. (slides)
Computability in Europe, Paris, France. June 2016.
Scott ranks of models of a theory. (slides)
ASL North American Annual Meeting, Storrs, CT. May 2016.
Scott ranks of models of a theory.
CUNY Model Theory Seminar, New York, NY. December 2015.
Differential-algebraic jet spaces and internality.
Kolchin Seminar in Differential Algebra, New York, NY. December 2015.
Scott ranks of models of a theory.
Notre Dame Logic Seminar, South Bend, IN. September 2015.
First-order possibility models and worldizations. (slides)
CSLI Workshop on Logic, Rationality, and Intelligent Interaction, Stanford, CA. May 2015.
Computable structures on a cone. (slides)
Sets and Computations, Singapore. April 2015.
Computable categoricity on a cone. (slides)
ASL North American Annual Meeting, Urbana-Champaign, IL. March 2015.
Computable functors and effective interpretability. (slides)
AMS Sectional Meeting, Georgetown, DC. March 2015.
Independence in computable algebra. (slides)
CMS Annual Meeting, Hamilton, Canada. Dec 2014.
Degree spectra of relations on a cone. (slides)
ASL Logic Colloquium, Vienna, Austria. July 2014.
Degree spectra of relations on a cone..
ASL North American Annual Meeting, Boulder, CO. May 2014.
Degree spectra of relations on a cone..
Graduate Student Conference in Logic, Madison, WI. April 2014.
Jet spaces are C-Moishezon.
McMaster Model Theory Seminar, Hamilton, Canada. November 2011.
Non-standard methods for bounds in differential polynomial rings.
Kolchin Seminar in Differential Algebra, New York, NY. October 2011.