Denis Roman Hirschfeldt

Citizenship

• Brazilian (permanent resident of the U.S.A.)

Research Interests

• 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 Delta⁰₂ 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 Delta⁰₂ 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.
• Pi⁰₁ 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.