Paul's Research

The bulk of my mathematical research is on reverse mathematics and on the degrees of unsolvability of mass problems.

Reverse Mathematics:  Reverse mathematics is a study of the logical strength of mathematical theorems in the context of second-order arithmetic.  The goal is to determine what axioms are necessary and sufficient to prove a given theorem.  To show that certain axioms suffice to prove a given theorem, all we need is a proof of that theorem from the axioms.  To show that certain axioms are necessary to prove a given theorem, we fix a set of weak axioms once-and-for-all and show that if the purported theorem is added to these weak axioms, then we can prove each of the stronger axioms we started with.  This means that the strong axioms were indeed necessary to prove the theorem.  The proofs of the strong axioms from the weak axioms and the given theorem are the "reverse" in "reverse mathematics."

Degrees of unsolvability of mass problems:  A mass problem is simply a set of functions thought of as an abstract mathematical problem, namely the problem of finding a function in that set.  The Medvedev and Muchnik degrees provide frameworks for analyzing the computational relationships among mass problems just as the classical Turing degrees provide a framework for analyzing the computational relationships among functions.  Under the interpretation of mass problems as mathematical problems, the Medvedev and Muchnik degrees formalize the "problem A is computationally harder than problem B" relationship.

Papers (the versions hosted here differ slightly from the official versions):

Selected Talks

My research in computer science consists of work on several projects in computational biology and the Biozon database led by Golan Yona.