Mathematical Logic, Computability Theory and Applications, Computable
Versions of Randomness, Kolmogorov Complexity, Reverse Mathematics
Education
Ph.D. in Mathematics, Cornell University, August 1999 (advisor:
Richard A. Shore).
M.S. in Computer Science, Cornell University, August 1998.
B.A. in Mathematics, University of Pennsylvania, May 1993.
Employment
Associate Professor, University of Chicago, from October 2005.
Assistant Professor, University of Chicago, September 2002 -
September 2005.
Dickson Instructor of Mathematics, University of Chicago, December
2000 - September 2002.
Postdoctoral Fellow, Victoria University of Wellington, August 1999 - December 2000.
Grants
National Science Foundation Research Grant 2002 - 2011.
Templeton Foundation "Exploring the Infinite" Program Grant
(with other researchers), 2008 - 2009.
National Science Foundation Focused Research Group Grant (with several
other researchers), 2007 - 2010.
National Science Foundation U.S.-Russia Binational Grant (with several
other researchers), 2006 - 2009.
Research Incentive Grant from the University of Chicago Department of
Computer Science, 2002.
Research Incentive Grant from the University of Chicago Department of
Mathematics, 2002 - 2005.
Associate investigator on a research grant from the Marsden Fund for
Basic Science of New Zealand, 2004 - 2006, awarded to the Department
of Computer Science, University of Auckland, New Zealand.
Honors and Awards
Visiting Scholar at the University of Notre Dame, April 2005.
Visiting Assistant Professorship at the University of
Wisconsin--Madison, September 2003.
1999 Sacks Prize of the Association for Symbolic Logic (best
doctoral dissertation in mathematical logic worldwide).
Honorary Fellowship at the University of Wisconsin-Madison, August - September 1999.
Alfred P. Sloan Doctoral Dissertation Fellowship, Spring 1998 - Fall 1999.
Research Fellowship at Victoria University of Wellington, supported by the Marsden Fund for Basic Science of New Zealand, October - November 1998.
Robert John Battig Prize of the Cornell Department of Mathematics, 1998.
Invited Talks and Refereed Conference Talks
Memorial Meeting in Honor of Andrei Muchnik, March 2008, Moscow,
Russia.
Special Session on Computability Thoery, Joint AMS-NZMS Meeting,
December 2007, Wellington, New Zealand.
Keynote Talk, Algorithmic-Logical Theory of Infinite Structures,
October - November 2007, Schloss Dagstuhl Research Center for Computer
Science, Germany.
Keynote Address, 8th Graduate Student Conference in Logic, April
2007, Chicago, IL.
Plenary Lecture, Association for Symbolic Logic Annual Meeting, March
2007, Gainesville, FL.
Workshop on Model Theory and Computable Model Theory, February 2007,
Gainesville, FL.
Tutorial on Algorithmic Randomness, Third International
Conference on Computability and Complexity in
Analysis, November 2006, Gainesville, FL.
Special Session on Computability Theory in Honor of
Manuel Lerman's Retirement, AMS Sectional
Meeting, October 2006, Storrs, CT.
Special Session on Randomness and Real Computation, Theory and
Applications of Models of Computation (TAMC 06), May 2006, Beijing,
China.
Special Session on Model Theory and Computability, AMS Sectional
Meeting, April 2006, South Bend, IN.
Kolmogorov Complexity and Applications, January - February 2006,
Schloss Dagstuhl Research Center for Computer Science, Germany.
Computational Prospects of Infinity, June - August 2005, Singapore.
11th Southeastern Logic Symposium, April 2005, Gainesville, FL.
Special Session on Computability and Randomness, Association for
Symbolic Logic Annual Meeting, March 2005, Stanford, CA.
UCLA Logic Meeting, February 2005, Los Angeles, CA.
Special Session on Reverse Mathematics, AMS Annual Meeting,
January 2005, Atlanta, GA.
North Texas Logic Conference, October 2004, Denton, TX.
10th Southeastern Logic Symposium, March 2004, Gainesville, FL.
Logic Section, 12th International Congress of Logic Methodology and
Philosophy of Science, August 2003, Oviedo, Spain.
Plenary Lecture, Greater Boston Logic Meeting, May 2003, Boston,
MA.
Kolmogorov Complexity and Applications, April 2003, Schloss
Dagstuhl Research Center for Computer Science, Germany.
Special Session on Computability and Models, AMS Annual Meeting,
January 2003, Baltimore, MD.
Special Session on Effectiveness Questions in Model Theory, AMS
Sectional Meeting, October 2002, Madison, WI.
Midwest Model Theory Meeting, April 2002, Chicago, IL.
Special Session on Computability Theory with Applications, AMS
Annual Meeting, January 2002, San Diego, CA.
Computability and Complexity in Analysis, November 2001, Schloss
Dagstuhl Research Center for Computer Science, Germany.
26th International Symposium on Mathematical Foundations of Computer
Science (MFCS 2001), August 2001, Mariánské Lázne, Czech
Republic.
Special Session on Computability Theory, Association for Symbolic
Logic European Summer Meeting, August 2001, Vienna, Austria.
Plenary Lecture, Association for Symbolic Logic
Annual Meeting, March 2001, Philadelphia, PA.
18th Annual Symposium on Theoretical Aspects of Computer Science
(STACS 2001), February 2001, Dresden, Germany.
Computability Theory Meeting, January 2001, Oberwolfach, Germany.
Plenary Lecture, Association for Symbolic Logic Winter Meeting,
January 2001, New Orleans, LA.
Plenary Lecture, Logic and Applications Meeting, May 2000,
Novosibirsk, Russia.
Special Session on Computability Theory, AMS Sectional Meeting,
March 1999, Gainesville, FL.
Special Session on Computability Theory, Association for Symbolic
Logic European Summer Meeting, August 1998, Prague, Czech Republic.
Special Session on Computability Theory, AMS Sectional Meeting,
October 1997, Milwaukee, WI.
Colloquia and seminars at various universities.
Courses Taught
Undergraduate Courses: Mathematical Logic I and II, Effective
Randomness, Algebra III,
Galois Theory, First Semester Calculus.
Graduate Courses: Set Theory I and II, Computable Model Theory I
and II, Intuitionistic Logic and Constructive Mathematics, Model
Theory III, Effective Randomness I and II, Effective Dimension,
Descriptive Set Theory I and II.
Graduate Students Examined or Advised
Associate advisor for Barbara Csima's Ph.D. Dissertation in Mathematics,
University of Chicago, 2003.
Associate advisor for Kenneth Harris's Ph.D. Dissertation in
Mathematics and Computer Science, University of Chicago, 2007.
Associate advisor for the following Ph.D. dissertations in
mathematics currently in progress at the University of Chicago: Karen
Lange, Rachel Epstein, Chris Conidis, Damir Dzhafarov, David Diamondstone.
Outside examiner for Sasha Rubin's Ph.D. Dissertation in Computer
Science, University of Auckland, New Zealand, 2004.
Outside examiner for Joseph Mileti's Ph.D. Dissertation in Mathematics,
University of Illinois at Urbana-Champaign, 2004.
Professional Activities and Memberships
Member of program committee for the Conference on Computability,
Complexity, and Randomness, Nanjing, China, 2008.
Co-organizer of the Workshop on Effective Randomness, Chicago, 2007.
Co-organizer of Topics in Computability: A Meeting in Honor of
Richard A. Shore, Boston, 2007.
Member of program committee for the Conference on Logic,
Computability, and Randomness, Buenos Aires, Argentina, 2007.
Member of program committee for the
Symposium on Logical Foundations of Computer Science (LFCS'07), New York,
2007.
Member of program committee for the Third International Conference on
Computability and Complexity in Analysis, Gainesville, FL, 2006.
Co-organizer of the Workshop on Effective Randomness at the American
Institute of Mathematics, 2006.
Member of the Association for Symbolic Logic Committee on
Meetings in North America, 2006 - present.
Member of an Association for Symbolic Logic Nominating Committee,
2005.
Reviews editor for the Bulletin of Symbolic Logic.
Member of program committee for the Conference on Logic,
Computability, and Randomness, Córdoba, Argentina, 2004.
Member of program committee for the Association for Symbolic Logic
2004 Annual Meeting, Pittsburgh, PA.
Member of program committee for the Association for Symbolic Logic
2003 Annual Meeting, Chicago, IL.
Member of organizing committee for the New Zealand Mathematics
Research Institute Summer Meeting, Kaikoura 2000, topic: computational
complexity.
Wrote the internal Journal of Symbolic Logic
database and its web-based interface in the programming language Perl.
Referee for various journals and reviewer for Mathematical
Reviews.
Member, American Mathematical Society, Association for Symbolic
Logic, and Mathematical Association of America.
List of Publications
Books
Editor (with R. G. Downey): Aspects of Complexity:
Minicourses in Algorithmics, Complexity, and Computational Algebra,
NZMRI Summer Meeting, Kaikoura, New Zealand, January 7 - 15, 2000,
de Gruyter Series in Logic and its Applications 4 (de Gruyter,
2001).
Algorithmic Randomness and Complexity (with R. G. Downey),
to be published by Springer-Verlag New York.
Articles in Refereed Journals and Conference Proceedings
Degree Spectra of Relations on Computable Structures,
Bulletin of Symbolic Logic 6 (2000), 197 - 212.
Undecidability and 1-types in Intervals of the Computably
Enumerable Degrees (with K. Ambos-Spies and R. A. Shore), Annals of
Pure and Applied Logic 106 (2000), 1 - 47.
Degree Spectra of Intrinsically C.E. Relations,
Journal of Symbolic Logic 66 (2001), 441 - 469.
Prime Models of Theories of Computable Linear Orderings,
Proceedings of the American Mathematical Society 129 (2001),
3079 - 3083.
A Delta02 Set with no Infinite Low Subset
in Either It or Its Complement (with R. G. Downey, S. Lempp, and
R. Solomon), Journal of Symbolic Logic 66 (2001), 1371 - 1381.
Degree Spectra and Computable Dimensions in Algebraic Structures
(with B. Khoussainov, R. A. Shore, and A. M. Slinko), Annals of
Pure and Applied Logic 115 (2002) 71 - 113.
Degree Spectra of Relations on Structures of Finite Computable
Dimension, Annals of Pure and Applied Logic 115 (2002) 233 -
277.
Randomness, Computability, and Density (with R. G. Downey and
A. Nies), SIAM Journal on Computing 31 (2002) 1169 - 1183
(extended abstract in A. Ferreira and H. Reichel (eds.), STACS 2001
Proceedings, Lecture Notes in Computer Science 2010 (Springer,
2001)).
Degree Spectra of Relations on Computable Structures in the
Presence of Delta02 Isomorphisms, Journal of
Symbolic Logic 67 (2002) 697 - 720.
Reverse Mathematics of the Nielsen-Schreier Theorem (with
R. G. Downey, S. Lempp, and R. Solomon), in Proceedings of
International Conferences on Mathematical Logic (Novosibirsk State
University Press, 2002) 59 - 71.
Realizing Levels of the Hyperarithmetic Hierarchy as Degree
Spectra of Relations on Computable Structures (with W. M. White), Notre
Dame Journal of Formal Logic 43 (2002) 51 - 64.
Degree Spectra of Relations on Boolean Algebras (with R. G. Downey
and S. S. Goncharov), Algebra and Logic 42 (2003) 105 - 111.
Trivial Reals (with R. G. Downey, A. Nies, and F. Stephan), in
R. Downey, D. Decheng, T. S. Ping, Q. Y. Hui, and M. Yasugi
(eds.),
Proceedings of the 7th and 8th Asian Logic Conferences
(Singapore University Press and World
Scientific, 2003) 103 - 131 (extended abstract in
Electronic Notes in Theoretical Computer Science 66).
Computability-Theoretic and Proof-Theoretic Aspects of Partial and
Linear Orderings (with R. G. Downey, S. Lempp, and R. Solomon), Israel
Journal of Mathematics 138 (2003) 271 - 290.
Uniformity in Computable Structure Theory (with R. G. Downey and
B. Khoussainov), Algebra and Logic 42 (2003) 318 - 332.
A Computably Categorical Structure Whose Expansion by a Constant Has
Infinite Computable Dimension (with B. Khoussainov and R. A. Shore),
Journal of Symbolic Logic 68 (2003) 1199 - 1241.
Randomness and Reducibility (with R. G. Downey and G. LaForte),
Journal of Computer and System Sciences 68 (2004), 96 - 114
(extended abstract in J. Sgall, A. Pultr, and
P. Kolman (eds.), Mathematical Foundations of Computer Science
2001, Lecture Notes in Computer Science 2136 (Springer, 2001),
316 - 327).
Bounding Prime Models (with B. F. Csima, J. F. Knight, and
R. I. Soare), Journal of Symbolic Logic 69 (2004) 1117 - 1142.
Relativizing Chaitin's Halting Probability (with R. Downey,
J. S. Miller, and A. Nies), Journal of Mathematical
Logic 5 (2005) 167 - 192.
Computable Trees, Prime Models, and Relative Decidability,
Proceedings of the American Mathematical Society 134 (2006)
1495 - 1498.
An Uncountably Categorical Theory whose Only Computably
Presentable Model Is Saturated (with B. Khoussainov and P. Semukhin),
Notre Dame Journal of Formal Logic 47 (2006) 63 - 71.
Calibrating Randomness (with R. Downey, A. Nies, and
S. A. Terwijn), Bulletin of Symbolic Logic 12 (2006) 411 - 491.
Every 1-Generic Computes a Properly 1-Generic (with B. F. Csima, R.
Downey, N. Greenberg, and J. S. Miller), Journal of
Symbolic Logic 71 (2006) 1385 - 1393.
Combinatorial Principles Weaker than Ramsey's Theorem for Pairs
(with R. A. Shore), Journal of
Symbolic Logic 72 (2007) 171 - 206.
Bounding Homogeneous Models (with B. F. Csima, V. S. Harizanov, and
R. I. Soare), Journal of Symbolic Logic 72 (2007) 305 - 323.
Pi01 Classes and Strong
Degree Spectra of Relations (with J. Chisholm, J. Chubb,
V. S. Harizanov, C. G. Jockusch, Jr., T. McNicholl, and S. Pingrey),
Journal of Symbolic Logic 72 (2007) 1003 - 1018.
Subspaces of Computable Vector Spaces (with R. Downey, A. M. Kach,
S. Lempp, J. R. Mileti, and A. Montálban),
Journal of Algebra 314 (2007) 888 - 894.
Using Random Sets as Oracles (with André Nies and Frank
Stephan), Journal of the London Mathematical
Society 75 (2007) 610 - 622.
Order Computable Sets (with R. Miller and S. Podzorov), Notre
Dame Journal of Formal Logic 48 (2007) 317 - 347.
Undecidability of the Structure of the Solovay Degrees of
C.E. Reals (with R. Downey and G. LaForte), Journal of
Computer and System Sciences 73 (2007) 769 - 787.
Limit Computability and Constructive Measure (with S. A. Terwijn), to
appear in the proceedings of the Program on Computational Prospects of
Infinity, Singapore 2005.
The Strength of Some Combinatorial Principles Related to Ramsey's
Theorem for Pairs (with C. G. Jockusch, Jr., B. Kjos-Hanssen,
S. Lempp, and T. A. Slaman), to appear in the proceedings of the
Program on Computational Prospects of Infinity, Singapore 2005.
The Atomic Model Theorem (with R. A. Shore and T. A. Slaman),
submitted.