I work in computability theory, a branch of logic that explores various computation models and uses these ideas to examine the computational content of problems. The bulk of my work is in computable structure theory, whose goal is to examine mathematical structures from an algorithmic perspective. For example, consider the set of real numbers (i.e., all numbers that can be written using the decimal system, e.g., 3.1415...).
In 1948, Tarski showed that the theory of the real numbers is computable. In other words, there is an algorithm that, given some statement about the real numbers (in terms of <, +, and ×), outputs whether the statement is true or false. By studying mathematical structures from a computational point of view, one obtains a deeper understanding of which aspects of these structures drive their overall complexity.
I study the computational complexity of various algebraic structures, including various kinds of graphs, groups, and homogeneous models, highly regular structures important in model theory. Some of my work from the computational perspective has led me to questions that are more algebraic or model-theoretic in nature. Separately, I am interested in aspects of the structure of the computably enumerable sets under inclusion, an object of intense study in classical computability theory.
Works in Progress
Lengths of developments in K((G)), J. Knight and K. Lange, in preparation.
Bounded low and high sets, B. Anderson, B. Csima, and K. Lange, submitted.
Note that the pdfs below are drafts. For the complete and best versions, please see the published papers.
Lattice of c.e. sets
D-maximal sets, P. Cholak, P. Gerdes, and K. Lange, Journal of Symbolic Logic, 80(4) (2015), 1182-1210.
On n-tardy sets, P. Cholak, P. Gerdes, and K. Lange,
Annals of Pure and Applied Logic, 163(9) (2012), 1252-1270. (pdf)
Computable structure theory
Classifications of structures, K. Lange, R. Miller, and R. Steiner, accepted by Notre Dame Journal of Formal Logic (2015).
Induction, bounding, weak combinatorial principles, and the homogeneous model theorem, D. Hirschfeldt, K. Lange, and R. Shore, accepted by Memoirs of the American Mathematical Society (2015).
The arithmetical hierarchy in the setting of ω1 computability, J. Carson, J. Johnson, J. Knight, K. Lange, C. McCoy, and J. Wallbaum, Computability, 2(2) (2013), 93-105. (pdf)
Complexity of structures associated with real closed fields, J. Knight and K. Lange, Proceedings of the London Mathematical Society, Third Series, 107(1) (2013), 177-197. (pdf)
Degrees of orders on torsion-free abelian groups, A. Kach, K. Lange, and D. Solomon, Annals of Pure and Applied Logic, 164(7-8) (2013), 822-836. (pdf)
Real closed exponential fields, P. D'Aquino, J. Knight, S. Kuhlmann, and K. Lange, Fundamenta Mathematicae, 219(2) (2012), 163-190. (pdf)
Describing free groups, J. Carson, V. Harizanov, J. Knight, K. Lange, C. Maher, C. McCoy, A. Morozov, S. Quinn, and J. Wallbaum, Transactions of the American Mathematical Society, 364(11) (2012), 5715-5728. (pdf)
Limit computable integer parts, P. D'Aquino, J. Knight, and K. Lange,
Archive for Mathematical Logic, 50(7-8) (2011), 681-695. (pdf)
Erratum Archive for Mathematical Logic, 54(3-4) (2015), 487-489.
A characterization of the 0-basis homogeneous bounding degrees, K. Lange, Journal of Symbolic Logic 75 No. 3 (2010), 971-995. (pdf)
The degree spectra of homogeneous models, K. Lange, Journal of Symbolic Logic, vol. 73 No. 3 (2008), 1009-1028. (pdf)
Computability of homogeneous models, K. Lange and R. Soare, Notre Dame Journal of Formal Logic, vol. 48 (2007), 143-170. (pdf)
The computational complexity of homogeneous models, K. Lange, Ph.D. thesis, Advisors: Robert Soare and Denis Hirschfeldt, University of Chicago (2008). (pdf)
Model theory and Weak arithmetic
Representing Scott sets in algebraic settings, A. Dolich, J. Knight, K. Lange, and D. Marker, Archive for Mathematical Logic, 54(5-6) (2015), 631-637.
A valuation theoretic characterization of recursively saturated real closed fields, P. D'Aquino, S. Kuhlmann, and K. Lange, Journal of Symbolic Logic, 80(1) (2015), 194-206.
Pattern, linesums, and symmetry, E.E. Eischen, C. R. Johnson, K. Lange, and D. Stanford, Linear Algebra and its Applications (LAA), vol. 357 (2002), 273-289.