Matthew Harrison-TrainorContactVictoria University of Wellington.Office: CO 430. Massey University Albany. Office: The Institute of Natural and Mathematical Sciences. Email: Curriculum VitaeMy CV.About MeI am currently a post-doctoral fellow working with Rod Downey at Victoria University of Wellington and Alexander Melnikov at Massey University. Previously 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. |
A minimal set low for speed (with Rod Downey)
Submitted for publication. [ pdf ]
An introduction to the Scott complexity of countable structures and a survey of recent results
Submitted for publication. [ pdf ]
Computing sets from all infinite subsets (with Noam Greenberg, Ludovic Patey, and Dan Turetsky)
Submitted for publication. [ pdf ]
Enumerations of families closed under finite differences (with Noam Greenberg, Joe Miller, and Dan Turetsky)
Submitted for publication. [ pdf ]
An analysis of random elections with large numbers of voters
Submitted for publication. [ pdf ]
There is a no simple characterization of the relatively decidable theories
Submitted for publication. [ pdf ]
Describing finitely presented algebraic structures
Submitted for publication. [ pdf ]
Some questions of uniformity in algorithmic randomness (with Laurent Bienvenu and Barbara Csima)
Submitted for publication. [ pdf ]
Which classes of structures are both pseudo-elementary and \(\mathcal{L}_{\omega_1 \omega}\)-elementary? (with Barbara Csima and Nancy Day)
Submitted for publication. [ pdf ]
A representation theorem for possibility models
Submitted for publication. [ pdf ]
Non-density in punctual computability (with Noam Greenberg, Alexander Melnikov, and Dan Turetsky)
Annals of Pure and Applies Logic, to appear. [ pdf ]
Relativizing computable categoricity (with Rod Downey and Alexander Melnikov)
Proceedings of the AMS, to appear. [ pdf ]
Relationships between computability-theoretic properties of problems (with Rod Downey, Noam Greenberg, Ludovic Patey, and Dan Turetsky)
Journal of Symbolic Logic, to appear. [ pdf ]
Scott complexity of countable structures (with Rachel Alvir, Noam Greenberg, and Dan Turetsky)
Journal of Symbolic Logic, to appear. [ pdf ]
The property “arithmetic-is-recursive” on a cone (with Uri Andrews and Noah Schweber)
Journal of Mathematical Logic, to appear. [ pdf ]
Computability up to homeomorphism (with Alexander Melnikov and Keng Meng Ng)
Journal of Symbolic Logic, to appear. [ pdf ]
The tree of tuples of a structure (with Antonio Montalbán)
Journal of Symbolic Logic, to appear. [ pdf ]
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.