Denis Roman Hirschfeldt

Citizenship

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

Research Interests

• Computability Theory, Computable Mathematics, Reverse Mathematics, Algorithmic Randomness

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

• Professor, University of Chicago, from October 2008.
• Associate Professor, University of Chicago, October 2005 - September 2008.
• 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 Grants, 2002 - 2014.
• National Science Foundation Focused Research Group Grant (with several other researchers), 2007 - 2011.
• Air Force Office of Scientific Research Grant, 2009.
• Templeton Foundation "Exploring the Infinite" Program Grant (with other researchers), 2008 - 2009.
• 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

• 2010 Shoenfield Prize of the Association for Symbolic Logic
• 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
• 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.

Talks

• Special Session on Effective Algebra and Model Theory, AMS Annual Meeting, January 2013, San Diego, CA.
• Invited Lecture, Logic and Computability Session, 4th Latin American Congress of Mathematicians, August 2012, Córdoba, Argentina.
• The Incomputable, June 2012, Chicheley Hall, UK.
• Plenary Lecture, 15th Latin American Symposium on Mathematical Logic, June 2012, Bogotá, Colombia.
• Special Session on Computability and its Applications, AMS Sectional Meeting, November 2010, South Bend, IN.
• Short Course on Reverse Mathematics of Combinatorial Principles, Asian Initiative for Infinity Summer School, July 2010, Singapore.
• Plenary Lecture, Computability in Europe, June - July 2010, Ponta Delgada, Portugal.
• 5th Conference on Logic, Computability, and Randomness, May 2010, South Bend, IN.
• Southeastern Logic Symposium, February 2010, Gainesville, FL.
• Special Session on Computability Theory, Logic Colloquium, August 2009, Sofia, Bulgaria.
• Foundational Adventures: A Conference in Honor of Harvey M. Friedman, May 2009, Columbus, OH.
• Marden Lecture, University of Wisconsin-Milwaukee, April 2009, Milwaukee, WI.
• Tutorial on Algorithmic Randomness, NZIMA / NZMRI summer workshop, January 2009, Napier, New Zealand.
• Computability, Reverse Mathematics, and Combinatorics, December 2008, Banff International Research Station, Canada.
• Special Session on Computability Theory and Effective Algebra, AMS Sectional Meeting, October 2008, Middletown, CT.
• Workshop on the Effective Mathematics of the Uncountable, August 2008, New York, NY.
• Memorial Meeting in Honor of Andrei Muchnik, March 2008, Moscow, Russia.
• Special Session on Computability Theory, 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 and Dimension, Point-Set Topology, 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, Advanced Topics in Logic

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 Karen Lange's Ph.D. Dissertation in Mathematics, University of Chicago, 2008.
• Associate advisor for Chris Conidis' Ph.D. Dissertation in Mathematics, University of Chicago, 2009.
• Associate advisor for Rachel Epstein's Ph.D. Dissertation in Mathematics, University of Chicago, 2010.
• Associate advisor for Damir Dzhafarov's Ph.D. Dissertation in Mathematics, University of Chicago, 2011.
• Associate advisor for David Diamondstone's Ph.D. Dissertation in Mathematics, University of Chicago, 2011.
• Associate advisor for the following Ph.D. dissertations in mathematics currently in progress at the University of Chicago: Matthew Wright, Jonathan Stephenson, Eric Astor.
• Outside examiner for Adam Day's Ph.D. Dissertation in Mathematics, Victoria University of Wellington, New Zealand, 2011.
• 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

• Editor for the Journal of Symbolic Logic, 2010 - 2012.
• Member of steering committee for the Computability, Complexity, and Randomness conference series, 2009 - present.
• Co-organizer of the Reverse Mathematics Workshop, Chicago, IL, 2011
• Member of program and organizing committees for Computability Theory and Applications: A Meeting in Honor of Robert I. Soare, Chicago, IL, 2011.
• Member of program committee for Computability in Europe 2011, Sofia, Bulgaria, 2011.
• Co-organizer of the Workshop on Computability Theory, Paris, France, 2010.
• Member of program committee for the 5th Conference on Logic, Computability, and Randomness, South Bend, IN, 2010.
• Member of program committee for the 2nd Workshop on the Effective Mathematics of the Uncountable, New York, 2009.
• Co-organizer of the Workshop on Reverse Mathematics: Foundations and Applications, Chicago, IL, 2009.
• Member of program committee for the 4th International Conference on Logic, Computability and Randomness, Luminy, France, 2009.
• Member of program committee for the Symposium on Logical Foundations of Computer Science (LFCS '09), Deerfield Beach, FL, 2009.
• Member of program committee for the Workshop on the Effective Mathematics of the Uncountable, New York, 2008.
• Member of program committee for the Conference on Computability, Complexity, and Randomness, Nanjing, China, 2008.
• Co-organizer of the Workshop on Effective Randomness, Chicago, IL, 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 - 2011.
• Member of an Association for Symbolic Logic Nominating Committee, 2005.
• Reviews editor for the Bulletin of Symbolic Logic, 2004 - 2008.
• 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.
• Wrote the internal Journal of Symbolic Logic database and its web-based interface.
• 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), Theory and Applications of Computability, Springer, New York, 2010.
• Editor (with N. Greenberg, R. Miller, and J. Hamkins) Effective Mathematics of the Uncountable, to appear in Lecture Notes in Logic, Association for Symbolic Logic / Cambridge University Press.

Papers

• 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), in Chong, Feng, Slaman, Woodin, and Yang (eds.), Computational Prospects of Infinity, Part II: Presented Talks, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 15, World Scientific 2008, 131 - 141.
• 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), in Chong, Feng, Slaman, Woodin, and Yang (eds.), Computational Prospects of Infinity, Part II: Presented Talks, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 15, World Scientific 2008, 143 - 161.
• The Atomic Model Theorem and Type Omitting (with R. A. Shore and T. A. Slaman), Transactions of the American Mathematical Society 361 (2009) 5805 - 5837.
• Finite self-information (with R. Weber), Computability 1 (2012) 85 - 98.
• Characterizing the strongly jump-traceable sets via randomness (with N. Greenberg and A. Nies), Advances in Mathematics 231 (2012) 2252 - 2293.
• On finitely presented expansions of computably enumerable semigroups (with B. Khoussainov), Algebra and Logic 51 (2012) 435 - 444.
• Counting the changes of random Delta⁰₂ sets (with S. Figueira, J. S. Miller, K. M. Ng, and A. Nies), to appear in the Journal of Logic and Computation.
• Categoricity properties for computable algebraic fields (with K. Kramer, R. Miller, and A. Shlapentokh), to appear in the Transactions of the American Mathematical Society.