Publications

My research is in computability (recursion) theory and in computable algebra and computable model theory (see my Chapter in Handbook of Recursive Mathematics and a Chapter in Turing's Legacy, co-authored with E. Fokina and A. Melnikov). Computability theory is the mathematical theory of algorithms. (See computability resource page.) Problems which can be solved algorithmically are called decidable. Undecidable problems can be more precisely classified by considering generalized algorithms, which require external knowledge. Turing degrees provide an important measure of the level of such knowledge needed. Computable model theory explores algorithmic properties of objects and constructions arising within mathematics. I am especially interested in computability-theoretic complexity of relations on algebraic structures, complexity of structures, and complexity of isomorphisms. I study orders on magmas and approximate computability. I am also interested in theoretical computer science, in particular, complexity theory, quantum computing, and algorithmic learning theory.

Papers in Refereed Journals and Volumes

Computability in infinite Galois theory and algorithmically random algebraic fields, co-authored with W. Calvert and A. Shlapentokh, submitted.
Generically computable linear orderings, co-authored with W. Calvert, D. Cenzer, and D. Gonzalez, submitted.
Cohesive powers of structures, co-authored with K. Srinivasan, accepted for publication in Archive for Mathematical Logic.
Generically computable Abelian groups and isomorphisms, co-authored with W. Calvert and D. Cenzer, submitted. Preliminary version in the Proceedings of Unconventional Computation and Natural Computation 2023, Springer, pp. 32-45.
Computability theory, co-authored with K. Srinivasan and D. Verta, in: Handbook on the History and Philosophy of Mathematical Practice, Springer, 2024.
Countable nonstandard models: following Skolem's approach, co-authored with R. Dimitrov, in: Handbook on the History and Philosophy of Mathematical Practice, Springer, 2024.
Computable isomorphism problem, in: Scientific Legacy of Professor Zbigniew Oziewicz, World Scientific (2023), pp. 671-693.
On cohesive powers of linear orders, co-authored with R. Dimitrov, A. Morozov, P. Shafer, A. Soskova, and S. Vatev, Journal of Symbolic Logic 88 (2023), pp. 947-1004.
Effective ultrapowers and applications, co-authored with R. Dimitrov, in: Aspects of Computation and Automata Theory with Applications, World Scientific (2023), pp. 201-221.
Generically and coarsely computable isomorphisms, co-authored with W. Calvert and D. Cenzer, Computability 11 (2022), pp. 223-239.
Interpreting a field in its Heisenberg group, co-authored with R. Alvir, W. Calvert, G. Goodman, J. Knight, A. Morozov, R. Miller, A. Soskova, and R. Weisshaar, Journal of Symbolic Logic 87 (2022), pp. 1215-1230.
On the isomorphism problem for some classes of computable algebraic structures, Archive for Mathematical Logic 61 (2022), pp.1215-1230.
Densely computable structures, co-authored with W. Calvert and D. Cenzer, Journal of Logic and Computation 32 (2022), pp. 581-607.
Computability and definability, co-authored with T. Ha, L. Marshall and H. Walker, chapter in: Structure and Randomness in Computability and Set Theory, World Scientific (2021), pp. 285-355.
On decidable categoricity and almost prime models, co-authored with S. Goncharov and R. Miller, Siberian Advances in Mathematics 30 (2020), pp. 200-212.
Turing degrees and automorphism groups of substructure lattices, co-authored with R. Dimitrov and A. Morozov, Algebra and Logic 59 (2020), pp. 18-32.
Turing degrees of complete formulas of almost prime models, co-authored with S. Goncharov and R. Miller, Algebra and Logic 58 (2019), communications paper, pp. 282-287.
Cohesive powers of linear orders, co-authored with R. Dimitrov, A. Morozov, P. Shafer, A. Soskova, and S. Vatev, in: Computing with Foresight and Industry, F. Manea, B. Martin, D. Paulusma and G. Primiero, eds., Springer (2019), pp.168-180.
Computability-theoretic categoricity and Scott families, co-authored with E. Fokina and D. Turetsky, Annals of Pure and Applied Logic 170 (2019), pp. 699-717.
Strong jump inversion, co-authored with W. Calvert, A. Frolov, J. Knight, C. McCoy, A. Soskova, and S. Vatev, Journal of Logic and Computation 7 (2018), pp.1499-1522.
Orders on magmas and computability theory, co-authored with T. Ha, Journal of Knot Theory and Ramifications 27 (2018), pp. 184001 (1-13).
Groups with orderings of arbitrary algorithmic complexity, co-authored with J. Chubb and M. Dabkowski, in Sets and Computations, R. Dilip, S.D. Friedman, and Y. Yang, eds., World Scientific (2017), pp. 221-251.
The lattice of computably enumerable vector spaces, co-authored with R. Dimitrov, in Computability and Complexity, A. Day, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov, and F. Rosamond, eds., Springer (2017), pp. 366-393.
Orbits of maximal vector spaces, co-authored with R. Dimitrov, journal Algebra and Logic 54 (2016), pp. 440-476.
Automorphism groups of substructure lattices of vector spaces in computable algebra, co-authored with R. Dimitrov and A. Morozov, in 12th Conference on Computability in Europe, A. Beckmann, L. Bienvenu, and N. Jonoska, eds., Springer (2016), pp. 251-260.
A (very) brief tour of quantum mechanics, computation, and category theory, with J. Chubb, in: Logic and Algebraic Structure in Quantum Computing, Cambridge University Press, 2016.
Index sets for n-decidable structures categorical relative to m-decidable presentations, co-authored with E. Fokina, S. Goncharov, O. Kudinov, and D. Turetsky, journal Algebra and Logic 54 (2015), pp. 336-341.
Turing degrees of the isomorphism types of geometric objects, co-authored with W. Calvert and A. Shlapentokh, journal Computability 3 (2014), pp. 105-134.
Computable model theory, co-authored with E. Fokina and A. Melnikov, chapter in Turing's Legacy: Developments from Turing Ideas in Logic, R. Downey, editor, Cambridge University Press (2014), pp. 124-194.
Computability-theoretic properties of injection structures, co-authored with D. Cenzer and J. Remmel, Algebra and Logic 53 (2014), pp. 39-69.
Isomorphisms of non-standard fields and Ash's conjecture, in: Language, Life, Limits, Computability in Europe, A. Beckman, E. Csuhaj-Varju, and K. Meer, eds., Springer (2014), pp. 143-152.
Two-to-one structures, co-authored with D. Cenzer and J. Remmel, Journal of Logic and Computation 23 (2013), pp. 1195-1223.
Describing free groups, co-authored with J. Carson, J. Knight, K. Lange, C. McCoy, A. Morozov, C. Safranski and J. Wallbaum, Transactions of the American Mathematical Society 364 (2012), pp. 5715-5728.
Isomorphism relations on computable structures, co-authored with E. Fokina, Sy-D. Friedman, J. Knight, C. McCoy and A. Montalban, Journal of Symbolic Logic 77 (2012), pp. 122-131.
The computable embedding problem, co-authored with J. Carson, E. Fokina, J. Knight, S. Quinn, C. Safranski and J. Wallbaum, Algebra and Logic 50 (2012), pp. 478-493.
Spectra of high_n and non-low_n degrees, with A. Frolov, I Kalimullin, O. Kudinov and R. Miller, Journal of Logic and Computation 22 (2012), pp. 755-777.
Co mputability of Fraisse limits, co-authored with B. Csima, R. Miller, and A. Montalban, Journal of Symbolic Logic 76 (2011), pp. 66-93.
S₁⁰ and P₁⁰ equivalence structures, co-authored with D. Cenzer and J. Remmel, Annals of Pure and Applied Logic 162 (2011), pp. 490-503.
Simple structures with complex symmetry, co-authored with R. Miller and A. Morozov, Algebra and Logic 49 (2010), pp.1134-1143.
Spaces of orders and their Turing degree spectra, co-authored with M. Dabkowska, M. Dabkowski, and A. Togha, Annals of Pure and Applied Logic 161 (2010), pp.1134-1143.
Intrinsic bounds on complexity at limit levels, co-authored with J. Chisholm, E. Fokina, S. Goncharov, J. Knight, S. Miller, Journal of Symbolic Logic 74 (2009), pp.1047-1060.
Effective c ategoricity of Abelian p-groups, co-authored with W. Calvert, D. Cenzer, and A. Morozov, Annals of Pure and Applied Logic 159 (2009), pp.187-197.
Degree spectra of the successor relation of computable linear orderings, co-authored with J. Chubb and A. Frolov, Archive for Mathematical Logic 48 (2009), pp. 7-13.
Chains and antichains in computable partial orderings, co-authored with C. Jockusch and J. Knight, Archive for Mathematical Logic 48 (2009), pp. 39-53.
Partial automorphism semigroups, co-authored with J. Chubb, A. Morozov, S. Pingrey, and E. Ufferman, Annals of Pure and Applied Logic 156 (2008), pp. 245-258.
P⁰1 classes and strong degree spectra of relations, co-authored with J. Chisholm, J.Chubb, D. Hirschfeldt, C. Jockusch, T. McNicholl, and S. Pingrey, Journal of Symbolic Logic 72 (2007), pp. 1003-1018.
Turing degrees of nonabelian groups, co-authored with M. Dabkowska, M. Dabkowski, and A. Sikora, Proceedings of the American Mathematical Society, 135 (2007), pp. 3383-3391.
Turing degrees of the isomorphism types of algebraic objects, co-authored with W. Calvert and A. Shlapentokh, Journal of the London Mathematical Society 73 (2007), pp. 273-286.
Compactness and spaces of left orders, co-authored with M. Dabkowska, M. Dabkowski, J. Przytycki, and M. Veve, Journal of Knot Theory and Its Ramifications 16 (2007), pp. 257-266.
Spectra of structures and relations, co-authored with R. Miller, Journal of Symbolic Logic 72 (2007), pp.324-348.
On the learnability of vector spaces, co-authored with F. Stephan, Journal of Computer and System Sciences 73 (2007), pp. 109-122.
Bounding homogeneous models, co-authored with B. Csima, D. Hirschfeldt, and R. Soare, Journal of Symbolic Logic 72 (2007), pp. 305-323.
Inductive inference systems for learning classes of algorithmically generated sets and structures, in: Induction, Algorithmic Learning Theory, and Philosophy (Springer, Dordrecht, 2007), pp. 27-54.
Introduction to the philosophy and mathematics of algorithmic learning theory, Induction, Algorithmic Learning Theory, and Philosophy (Springer, Dordrecht, 2007), pp. 1-24.
Index sets of computable structures, co-authored with W. Calvert, J. Knight, and S. Miller, Algebra and Logic 45 (2006), pp. 306-325.
Formal approaches to modality, co-authored with S. Kaufmann and C. Condoravdi, The Expression of Modality, W. Frawley (editor), Mouton de Gruyter, Berlin, 2006, pp. 71-106. Editor's Preface
Effective categoricity of equivalence structures, co-authored with W. Calvert, D. Cenzer, and A. Morozov, Annals of Pure and Applied Logic 141 (2006), pp. 61-78.
Enumerations in computable structure theory, co-authored with S. Goncharov, J. Knight, C. McCoy, R. Miller, and R. Solomon, Annals of Pure and Applied Logic 136 (2005), pp. 219-246.
On automorphic tuples of elements in computable models, co-authored with S. Goncharov, J. Knight, A. Morozov, and A. Romina, Siberian Mathematical Journal 46, 2005, pp. 523-532 (Russian); pp. 405-412 (English translation). Russian version.
Dependence relations in computably rigid computable vector spaces , co-authored with R. Dimitrov, and A. Morozov, Annals of Pure and Applied Logic 132, 2005, pp. 97-108.
P¹₁ relations and paths through O, co-authored with S. Goncharov, J. Knight, and R. Shore, Journal of Symbolic Logic 69, 2004, pp. 585-611.
Relatively hyperimmune relations on structures, co-authored with S. Goncharov, J. Knight, and C. McCoy, Algebra and Logic 43, 2004, pp. 94-101.
Trivial, strongly minimal theories are model complete after naming constants, co-authored with S. Goncharov, M. Laskowski, S. Lempp, and C. McCoy, Proceedings of the American Mathematical Society 131, 2003, pp.3901-3912.
Turing degrees of hypersimple relations on computable structures, Annals of Pure and Applied Logic 121, 2003, pp. 209-226.
Simple and immune relations on countable structures, co-authored with S. Goncharov, J. Knight, and C. McCoy, Archive for Mathematical Logic 42, 2003, pp. 279-291.
Computably-theoretic complexity of countable structures, Bulletin of Symbolic Logic 8, 2002, pp. 457-477.
Sequences of n-diagrams, co-authored with J Knight and A. Morozov, Journal of Symbolic Logic 67, 2002, pp.1227-1247.
Relations on computable structures, Contemporary Mathematics, N. Bokan (editor), devoted to the 125^th anniversary of the Department of Mathematics, University of Belgrade, 2000, pp. 65-81.
Effectively nowhere simple relations on computable structures, in: Recursion Theory and Complexity, vol. 2, M. Arslanov, and S. Lempp (editors), de Gruyter, Berlin, 1999, pp. 59-70.
Pure Computable Model Theory, chapter in: Handbook of Recursive Mathematics, vol. I, Yu. Ershov, S. Goncharov, A. Nerode, and J. B. Remmel (editors), North-Holland, Amsterdam, 1998, pp. 3-114.
Turing degrees of certain isomorphic images of recursive relations, Annals of Pure and Applied Logic 93, 1998, pp. 103-113.
Effectively and non-effectively nowhere simple sets, Mathematical Logic Quarterly 42, 1996, pp. 241-248.
The possible Turing degree of the nonzero member in a two-element degree spectrum, Annals of Pure and Applied Logic 60, 1993, pp. 1-30.
Frequency computations and the cardinality theorem, co-authored with M. Kummer, and J. Owings, Journal of Symbolic Logic 57, 1992, pp. 682-687.
Some effects of Ash-Nerode and other decidability conditions on degree spectra, Annals of Pure and Applied Logic 55, 1991, pp. 51-65.
Uncountable degree spectra, Annals of Pure and Applied Logic 54, 1991, pp. 255-263.
Regular relations and the quantifier there exists uncountably many, co-authored with Z. Mijajlovic, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik 29, 1983, pp. 151-161.
On some finite groupoids whose equational theories are not finitely based, in: Algebraic Conference, Mathematical Institute, Novi Sad, 1982, pp. 35-38.
On the functional equation fgf=f, Publications de l Institut Mathematique, Nouvelle Serie 29, 1981, pp. 61-64.

Edited Books and Special Issues of Journals

Logic and Algebraic Structures in Quantum Computing, co-edited with J. Chubb and A. Eskandarian, Cambridge University Press, March 2016. Introduction.
Induction, Algorithmic Learning Theory, and Philosophy, co-edited with M. Friend and N.B. Goethe, Series Logic, Epistemology, and the Unity of Science, vol. 9, Springer, 304 pp., 2007. ISBN: 978-1-4020-6126-4. Editors' preface
Journal of Knot Theory and Its Ramifications, vol. 30, nos. 12–14, dedicated to the 60th birthday of Jozef Przytycki (vol. IV), co-edited with M. Dabkowski, L. Kauffman, J. Przytycki, R. Sazdanovic, and A. Sikora, World Scientific, Singapore, 2021.
Journal of Knot Theory and Its Ramifications , vol. 27, no. 3, dedicated to the 60th birthday of Jozef Przytycki (vol. III), co-edited with M. Dabkowski, L. Kauffman, J. Przytycki, R. Sazdanovic, and A. Sikora, World Scientific, Singapore, March 2018.
Journal of Knot Theory and Its Ramifications, vol. 26, no. 3, dedicated to the 60th birthday of Jozef Przytycki (vol. II), co-edited with M. Dabkowski, L. Kauffman, J. Przytycki, R. Sazdanovic, and A. Sikora, World Scientific, Singapore, March 2017.
Journal of Knot Theory and Its Ramifications, vol. 25, no. 3, dedicated to the 60th birthday of Jozef Przytycki (vol. I), co-edited with M. Dabkowski, L. Kauffman, J. Przytycki, R. Sazdanovic, and A. Sikora, World Scientific, Singapore, March 2016.
Journal of Knot Theory and Its Ramifications Special Issue: The Workshop on Knots and Quantum Computing, vol. II, co-edited with M. Dabkowski, L. Kauffman, J. Przytycki and V. Ramakrishna, vol. 20, no. 1, World Scientific, Singapore, 335 pp., January 2011.
Journal of Knot Theory and Its Ramifications Special Issue: The Workshop on Knots and Quantum Computing, vol. I, co-edited with M. Dabkowski, L. Kauffman, J. Przytycki and V. Ramakrishna, vol. 19, no. 6, World Scientific, Singapore, 127 pp., June 2010.
Archive for Mathematical Logic Special Issue: The Workshop on Model Theory and Computable Model Theory, co-edited with D. Cenzer, D. Marker and C. Wood, vol. 48, no. 1, Springer, Berlin, 140 pp., February 2009.

Invited Book Reviews and AMS Notices

In memory of Martin Davis, co-authored with W. Calvert, E. Omodeo, A. Policriti and A. Shlapentokh, to appear in the Notices of the American Mathematical Society, 2024.
Computable Structures and Hyperarithmetical Hierarchy by C.J. Ash and J. Knight, V. Harizanov, Bulletin of Symbolic Logic 3, 2001, pp. 383-385.
Countable Boolean Algebras and Decidability by S. Goncharov, V. Harizanov, Journal of Symbolic Logic 63, 1998, pp. 1188-1190.
Y. Matiyasevich, Hilbert s Tenth Problem, V. Harizanov, Modern Logic (International Journal for the History of Mathematical Logic, Set Theory, and Foundations of Mathematics) 5, 1995, pp. 345-355.
Douglas Hofstadter (a review of Goedel, Escher, Bach), V. Harizanov GW Forum, Spring, 1988, pp. 46-48.

Translations

M. V. Zakharyashchev, Modal companions of superintuitionistic logics: syntax, semantics, and preservation theorems, Mathematics of the USSR Sbornik 68 (1991), pp. 277-289. Translated from Russian by V. Harizanov.
A. I. Tsitkin, Towards the question of an error in a well-known paper by M. Wajsberg, Selecta Mathematica Sovietica 7, 1988, pp. 23-36. Translated from Russian by V. Harizanov.
V. P. Orevkov, Theorems with very short proofs can be strengthened, Selecta Mathematica Sovietica 7, 1988, pp. 37-38. Translated from Russian by V. Harizanov.
I. D. Zaslavsky, The realization of three-valued logical functions through recursive and Turing operators, Selecta Mathematica Sovietica 7, 1988, pp. 15-22. Translated from Russian by V. Harizanov.
K. Zh. Kudaibergenov, On questions of Keisler and Morley, Soviet Mathematics Doklady (Russian Academy of Sciences) 34, 1987, pp. 482-483. Translated from Russian by V. Harizanov.
N. V. Petri, Unsolvability of the recognition problem for annihilating iterative networks, Selecta Mathematica Sovietica 6, 1987, pp. 355-363. Translated from Russian by V. Harizanov.
N. K. Zamov, The resolution method without skolemization, Soviet Mathematics Doklady (Russian Academy of Sciences) 35, 1987, pp. 399-401. Translated from Russian by V. Harizanov.
D. P. Skvortsov, Some propositional logics connected with Yu. T. Medvedev concept of types of information, Selecta Mathematica Sovietica 5, 1986, pp. 371-377. Translated from Russian by V. Harizanov.
L. L. Esakia, On the variety of Grzegorczyk algebras, Selecta Mathematica Sovietica 3, 1983/84, pp. 343-366. Translated from Russian by V. Harizanov.

Coauthors

Wesley Calvert, Mathematics, Southern Illinois University
Doug Cenzer, Mathematics, University of Florida
Cleo Condoravdi, Stanford University
Barbara Csima, Pure Mathematics, University of Waterloo, Canada
Mietek Dabkowski, Mathematical Sciences, University of Texas at Dallas
Ekaterina Fokina, Vienna University of Technology, Vienna
Sy Friedman, Kurt Goedel Research Center, Vienna
Sergey Goncharov, Mathematics, Novosibirsk State University and Russian Academy of Sciences
Denis Hirschfeldt, Mathematics, University of Chicago
Carl Jockusch, Jr., Mathematics, University of Illinois at Urbana-Champaign
Stefan Kaufmann, Linguistics, University of Connecticut
Julia Knight, Mathematics, University of Notre Dame
Karen Lange, Mathematics, Wellesley College
Chris Laskowski, Mathematics, University of Maryland
Steffen Lempp, Mathematics, University of Wisconsin
Charlie McCoy, Mathematics, University of Portland
Alexander Melnikov, School of Mathematics and Statistics, Victoria University of Wellington New Zealand
Russell Miller, Mathematics, CUNY
Antonio Montalban, Mathematics, University of California, Berkeley
Andrei Morozov, Mathematics, Novosibirsk State University and Russian Academy of Sciences
Jozef Przytycki, Mathematics, George Washington University
Jeffrey Remmel, Mathematics, also Computer Science, University of California, San Diego
Adam Sikora, Mathematics, State University of New York at Buffalo
Alexandra Shlapentokh, Mathematics, East Carolina University
Richard Shore, Mathematics, Cornell University
Robert Soare, Mathematics, University of Chicago
Reed Solomon, Mathematics, University of Connecticut
Frank Stephan, Computer Science, also Mathematics, National University of Singapore