Peter Cholak
Professor
B.S., Union College, 1984
M.S., M.A., University of Wisconsin, 1988
Ph.D., University of Wisconsin, 1991
Email: Peter.Cholak.1@nd.edu
Office: 122 HayesHealy
Phone: (574) 6316507
Fax: (574) 6316579
For additional information see Peter Cholak’s Personally Maintained Page.
Research Interests
The area of mathematics that I am most interested in is Computability Theory, which is also known as Recursion Theory. In particular, I am interested in the relationship between computational complexity and various other mathematical objects.
Two common measures of computation complexity are the Turing and polynomialtime reducibilities, but there are many others. Some examples of this relationship from my work: every nontrivial orbit in the lattice of enumerable sets contains a set with a high Turing degree, the question of whether a logic program is locally stratified is undecidable and the theory of the parameterized polynomial time degrees is undecidable and every computable 2 coloring of pairs of natural numbers has a low$_2$ homogeneous set. The last example is particularly interesting since its proof can be used to show the firstorder consequences of Ramsey Theorem for pairs is a subset of the firstorder consequences of RCA$_0$ plus induction for $\Sigma^0_3$ formulas. There are many other examples in the literature.
Selected Publications

Cholak, Peter A.; Downey, Rodney; Harrington, Leo A. On the orbits of computably enumerable sets. J. Amer. Math. Soc. 21 (2008), no. 4, 11051135.

Cholak, Peter; Downey, Rod; Greenberg, Noam Strong jumptraceabilty. I. The computably enumerable case. Adv. Math. 217 (2008), no. 5, 20452074.

Cholak, Peter A.; Harrington, Leo A. Extension theorems, orbits, and automorphisms of the computably enumerable sets. Trans. Amer. Math. Soc. 360 (2008), no. 4, 17591791.

Cholak, Peter; Greenberg, Noam; Miller, Joseph S. Uniform almost everywhere domination. J. Symbolic Logic 71 (2006), no. 3, 10571072
If you have access to MathSciNet you can see a complete list of publications.
Please direct questions and comments to: Peter.Cholak.1@nd.edu