Paul's Research

• David Fernández-Duque, Paul Shafer, Henry Towsner, and Keita Yokoyama.  Metric fixed point theory and partial impredicativity.  Philosophical Transactions of the Royal Society A 381 (2022).  no. 2248.  Theme issue 'Modern perspectives in proof theory.'  Aguilera, Pakhomov, Weiermann editors.  pdf  arXiv
  
  
• Paul Shafer.  Effective powers of omega over Delta_2 cohesive sets and infinite Pi_1 sets without Delta_2 cohesive subsets.  preprint.  pdf  arXiv
  
  
• Marta Fiori-Carones, Alberto Marcone, Paul Shafer, and Giovanni Soldà.  (Extra)ordinary equivalences with the ascending/descending sequence principle.  Journal of Symbolic Logic (2022).  1–46.  pdf  arXiv
  
  
• Paul Shafer and Sebastiaan A. Terwijn.  Ordinal analysis of partial combinatory algebras.  Journal of Symbolic Logic 86 (2021).  no. 3.  1154–1188.  pdf  arXiv
  
  
• Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul Shafer, Alexandra A. Soskova, and Stefan V. Vatev.  On cohesive powers of linear orders.  Journal of Symbolic Logic 88 (2023).  no. 3.  947–1004.  pdf  arXiv
  
  
• Marta Fiori-Carones, Paul Shafer, and Giovanni Soldà.  An inside/outside Ramsey theorem and recursion theory.  Transactions of the American Mathematical Society 375 (2022).  no. 3.  1977–2024.  pdf  arXiv
  
  
• Paul Shafer.  The strength of compactness for countable complete linear orders.  Computability 9 (2020).  no. 1.  25–36.  pdf  arXiv
  
  
• David Fernández-Duque, Paul Shafer, and Keita Yokoyama.  Ekeland's variational principle in weak and strong systems of arithmetic.  Selecta Mathematica, New Series 26 (2020).  no. 5.  Paper no. 68.  38pp.  pdf  arXiv
  
  
• André Nies and Paul Shafer.  Randomness notions and reverse mathematics.  Journal of Symbolic Logic 85 (2020).  no. 1.  271–299.  pdf  arXiv
  
  
• Paul Shafer and Andrea Sorbi.  Comparing the degrees of enumerability and the closed Medvedev degrees.  Archive for Mathematical Logic 58 (2019).  no. 5-6.  527–542.  pdf  arXiv
  
  
• Paul Shafer.  Honest elementary degrees and degrees of relative provability without the cupping property.  Annals of Pure and Applied Logic 168 (2017).  no. 5.  1017–1031.  pdf  arXiv
  
  
• Paul Shafer.  The reverse mathematics of the Tietze extension theorem.  Proceedings of the American Mathematical Society 144 (2016).  no. 12.  5359–5370.  pdf  arXiv
  
  
• Emanuele Frittaion, Matthew Hendtlass, Alberto Marcone, Paul Shafer, and Jeroen Van der Meeren.  Reverse mathematics, well-quasi-orders, and Noetherian spaces.  Archive for Mathematical Logic 55 (2016).  no. 3-4.  431–459.  pdf  arXiv
  
  
• Laurent Bienvenu, Ludovic Patey, and Paul Shafer.  On the logical strengths of partial solutions to mathematical problems.  Transactions of the London Mathematical Society 4 (2017).  no. 1.  30–71.  pdf  arXiv
  
  
• Rupert Hölzl and Paul Shafer.  Universality, optimality, and randomness deficiency.  Annals of Pure and Applied Logic 166 (2015).  no. 10.  1049–1069.  pdf  arXiv
  
  
• François G. Dorais, Jeffry L. Hirst, and Paul Shafer.  Comparing the strength of diagonally non-recursive functions in the absence of Sigma^0_2 induction.  Journal of Symbolic Logic 80 (2015).  no. 4.  1211–1235.  pdf  arXiv
  
  
• Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter, and Paul Shafer.  Randomness and semi-measures.  Notre Dame Journal of Formal Logic 58 (2017).  no. 3.  301–328.  pdf  arXiv
  
  
• François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer.  On uniform relationships between combinatorial problems.  Transactions of the American Mathematical Society 368 (2016).  no. 2.  1321–1359.  pdf  arXiv
  
  
• François G. Dorais, Jeffry Hirst, and Paul Shafer.  Reverse mathematics and algebraic field extensions.  Computability 2 (2013).  no. 2.  75–92.  pdf  arXiv
  
  
• François G. Dorais, Jeffry Hirst, and Paul Shafer.  Reverse mathematics, trichotomy, and dichotomy.  Journal of Logic and Analysis 4 (2012).  Paper no. 13.  14pp.  pdf
  
  
• Paul Shafer.  Menger's theorem in Pi^1_1-CA_0.  Archive for Mathematical Logic 51 (2012).  no. 3-4.  407–423.  pdf
  
  
• Paul Shafer.  Coding true arithmetic in the Medvedev degrees of Pi^0_1 classes.  Annals of Pure and Applied Logic 163 (2012).  no. 3.  321–337.  pdf
  
  
• Paul Shafer.  Coding true arithmetic in the Medvedev and Muchnik degrees.  Journal of Symbolic Logic 76 (2011).  no. 1.  267–288.  pdf
  
  
• Paul Shafer.  Characterizing the join-irreducible Medvedev degrees.  Notre Dame Journal of Formal Logic 52 (2011).  no. 1.  21–38.  pdf
  

• Paul Shafer.  On the complexity of mathematical problems: Medvedev degrees and reverse mathematics.  PhD thesis.  Cornell University, 2011.  pdf
  

• Ordinal analysis of partial combinatory algebras.  Given at From 𝜔 to 𝛺 in Singapore on June 16, 2023 and at Computability, Complexity, and Randomness 2023 in Kochel, Germany on July 10, 2023.
  
  
• The Rival–Sands theorem for partial orders, ascending/descending sequences, and Sigma_2 induction.  Given at the Tohoku University Logic Seminar in Sendai, Japan on June 9, 2023.
  
  
• The complexity of inside/outside Ramsey theorems.  5-hour course given at the Computability and Combinatorics 2023 Summer School in Hartford, Connecticut during May 15–18, 2023.
  
  
• The Medvedev and Muchnik degrees.  Given at Logique à Paris 2023 in Paris, France on May 11, 2023.
  
  
• Usual theorems of unusual strength.  Given at the Séminaire de Logique in Paris, France on November 28, 2022 and at the British Logic Colloquium Annual Meeting in Bristol, England on September 8, 2023.
  
  
• The logical and computational strength of inside/outside Ramsey theorems.  Given at the Warsaw Mathematical Logic Seminar (virtual) on May 18, 2022; at the Workshop on Reverse Mathematics and its Philosophy in Paris, France on June 13, 2022; and at the Two-Day Logic Meeting in Bristol, England on July 1, 2023.
  
  
• Reverse mathematics and topology.  Given at the Western Illinois University Mathematics Colloquium (virtual) on December 2, 2021.
  
  
• An inside-outside Ramsey theorem in the Weihrauch degrees.  Given at the Swansea University Computer Science Seminar in Swansea, Wales on January 21, 2020 and at the Turin–Udine Logic Seminar (virtual) on February 19, 2021.
  
  
• Randomness notions and reverse mathematics.  Given at Proof Theory, Modal Logic, and Reflection Principles 2019 in Barcelona, Spain on November 6, 2019 and at the Computability Theory and Applications Online Seminar / Midwest Computability Seminar (virtual) on November 10, 2020.
  
  
• Exploring the strength of Caristi's fixed point theorem and Ekeland's variational principle.  Given at the University of Bristol Logic and Set Theory Seminar in Bristol, England on October 23, 2019.
  
  
• Reverse mathematics of an inside/outside Ramsey theorem.  Given at Reverse Mathematics of Combinatorial Principles in Oaxaca, Mexico on September 20, 2019.
  
  
• Cohesive powers of linear orders.  Given at Computability in Europe 2019 in Durham, England on July 15, 2019; at Logic Colloquium 2019 in Prague, Czech Republic on August 12, 2019; at the Computability Theory Seminar of the MSRI program on Decidability, Definability and Computability in Number Theory (virtual) on October 30, 2020; at Joint Mathematics Meetings 2021 (virtual) on January 7, 2021; and at the Manchester Logic Seminar in Manchester, England on May 25, 2022.
  
  
• An introduction to computable functions and computable structures.  Given at the General Meeting of the London Mathematical Society in London, England on June 28, 2019.
  
  
• PhD short course on Medvedev and Muchnik degrees.  10-hour course given at the University of Udine in Udine, Italy during September 24–28, 2018.
  
  
• Reverse mathematics, a Ramsey theorem for graphs, and complete linear orders.  Given at the Workshop on Ramsey Theory and Computability in Rome, Italy on July 9, 2018.
  
  
• Reverse mathematics of Caristi's fixed point theorem and Ekeland's variational principle.  Given at ASL North American Annual Meeting 2018 in Macomb, Illinois on May 19, 2018 and at Workshop: Proofs and Computation in Bonn, Germany on July 2, 2018.
  
  
• The reverse mathematics of Ekeland's variational principle.  Given at Proof Theory, Modal Logic, and Reflection Principles 2017 in Moscow, Russia on October 17, 2017.
  
  
• The reverse mathematics of Caristi's fixed point theorem.  Given at the 11^th Panhellenic Logic Symposium in Delphi, Greece on July 13, 2017 and at the University of Manchester Logic Seminar in Manchester, England on November 29, 2017.
  
  
• Honest elementary degrees without the cupping property.  Given at Computability in Europe 2016 in Paris, France on June 28, 2016; at Proof Theory, Modal Logic, and Reflection Principles Third International Wormshop in Tbilisi, Georgia on September 8, 2016; and at the Conference on Mathematical Logic in Gyolechitsa, Bulgaria in honor of Dimiter Skordev's 80th birthday on October 8, 2016.
  
  
• A tour of the mass problems.  Given at The Foundational Impact of Recursion Theory in Storrs, Connecticut in honor of Steve Simpson's 70th birthday on May 22, 2016.
  
  
• Reverse mathematics and the strong Tietze extension theorem.  Given at the New Challenges in Reverse Mathematics Workshop in Singapore on January 11, 2016 and at Computability Theory and Foundations of Mathematics 2016 in Tokyo, Japan on September 20, 2016.
  
  
• Universality, optimality, and randomness deficiency.  Given at Varieties of Algorithmic Information in Heidelberg, Germany on June 18, 2015 and at Logic Colloquium 2015 in Helsinki, Finland on August 4, 2015.
  
  
• Reverse mathematics, well-quasi-orders, and Noetherian spaces.  Given at the Sets and Computations Workshop in Singapore on April 20, 2015 and at Computability in Europe 2015 in Bucharest, Romania on July 2, 2015.
  
  
• Exploring randomness, diagonally non-recursiveness, and Ramsey-type combinatorial principles in reverse mathematics.  Given at ASL North American Annual Meeting 2014 in Boulder, Colorado on May 21, 2014 and at Proof Theory, Modal Logic, and Reflection Principles Second International Wormshop in Mexico City, Mexico on September 30, 2014.
  
  
• Studying the role of induction axioms in reverse mathematics.  Given at the Sendai Logic School in Tokyo, Japan on February 21, 2014.
  
  
• Separating the uniformly computably true from the computably true via strong Weihrauch reducibility.  Given at Computability Theory and Foundations of Mathematics 2014 in Tokyo, Japan on February 17, 2014.
  
  
• Examples of problems that cannot be solved by randomness and examples of problems that can be solved by randomness.  Given at the University of Udine Department of Mathematics and Computer Science Seminar in Udine, Italy on September 17, 2013 and at the Sendai Logic Seminar in Sendai, Japan on February 14, 2014.
  
  
• Reverse mathematics and Birkhoff’s problem 111.  Given at the Bundeswehr University Munich Seminar for Theoretical Computer Science and Mathematical Logic in Munich, Germany on August 21, 2013.
  
  
• Comparing the strength of DNR(k) functions and DNR(2) functions.  Given at Logic Colloquium 2013 in Évora, Portugal on July 22, 2013.
  
  
• A low DNR(k) function that computes no DNR(2) function.  Given at the Workshop on Reverse Mathematics and Type Theory in Seoul, South Korea on March 26, 2013 and at Journées Calculabilités 2013 in Nancy, France on April 11, 2013.
  
  
• Randomness from an algorithmic perspective.  Given at the ENS Lyon Semaine Sport-Etudes 2012-2013 in Les 7 Laux, France on January 26, 2013.
  
  
• Logics and complexity in a calculus of problems.  Given at the Ghent University Logic and Analysis Seminar in Ghent, Belgium on October 24, 2012.
  
  
• Presenting the effectively closed Medvedev degrees requires 0'''.  Given at ASL North American Annual Meeting 2012 in Madison, Wisconsin on March 31, 2012.
  
  
• The Medvedev degrees as semantics for propositional logic.  Given at AMS Spring Eastern Sectional Meeting 2012 in Washington, DC on March 18, 2012.
  
  
• Complexity in the degrees of unsolvability of mass problems.  Given at ASL Winter Meeting 2012 in Boston, Massachusetts on January 6, 2012.
  
  
• Complexity in the Medvedev and Muchnik degrees.  Given at the Penn State Logic Seminar in State College, Pennsylvania on October 14, 2011.
  
  
• Describing the complexity of the "problem B is harder than problem A" relation.  Given at the Appalachian State University Mathematical Sciences Colloquium in Boone, North Carolina on October 7, 2011.
  
  
• Complexity in the Medvedev degrees of Pi^0_1 classes.  Given at Workshop on Computability Theory 2011, part 2 in Barcelona, Spain on July 17, 2011.
  
  
• Birkhoff's theorem and reverse mathematics.  Given at AMS Fall Central Sectional Meeting 2010 in Notre Dame, Indiana on November 7, 2010.
  
  
• Medvedev degrees:  characterizing the first-order theory and the join-irreducibles.  Given at the Notre Dame Logic Seminar in Notre Dame, Indiana on November 4, 2010.
  
  
• Menger's theorem in Pi^1_1-CA_0.  Given at Logic Colloquium 2010 in Paris, France on July 27, 2010.
  
  
• Coding second-order arithmetic into the closed Medvedev degrees.  Given at ASL North American Annual Meeting 2010 in Washington, DC on March 17, 2010.
  
  
• The first-order theory of the Medvedev lattice is third-order arithmetic.  Given at Logic Colloquium 2009 in Sofia, Bulgaria on August 4, 2009.
  
  
• A characterization of the join-irreducible Medvedev degrees.  Given at Computability in Europe 2009 in Heidelberg, Germany on July 22, 2009.
  
  
• Menger's theorem and reverse mathematics.  Given at the MIT Logic Seminar in Cambridge, Massachusetts on April 2, 2008.

• Eric O. Williams, Yuanyuan Xiao, Heather M. Sickles, Paul Shafer, Golan Yona, Jean YH Yang, and David M. Lin.  Novel subdomains of the mouse olfactory bulb defined by molecular heterogeneity in the nascent external plexiform and glomerular layers.  BMC Developmental Biology 7:48 (2007).
  
  
• Paul Shafer, David M. Lin, and Golan Yona.  EST2Prot: Mapping EST sequences to proteins.  BMC Genomics 7:41 (2006).
  
  
• Paul Shafer, Timothy Isganitis, and Golan Yona.  Hubs of knowledge: using the functional link structure of Biozon to mine for biologically significant entities.  BMC Bioinformatics 7:71 (2006).

• Paul Shafer and Timothy Isganitis.  Hubs of Knowledge: using the functional link structure in Biozon to mine for biologically significant entities.  Given at ISMB 2005 in Detroit, Michigan on June 28, 2005.