Professor Stephen Jackson invites you to attend the Doctoral Dissertation Defense of Alex Creiner

ABSTRACT: As soon as Bennett and Gill first demonstrated that, relative to a randomly chosen oracle, P did not equal NP with probability 1, the random oracle hypothesis began piquing the interest of mathematicians and computer scientists. This was quickly disproven in several ways, most famously in 1992 with the result that IP = PSPACE, despite the classes being previously shown unequal with probability 1. Here, we propose what could be considered strengthening of the random oracle hypothesis, using a stricter notion of what it means for a set to be 'large'. In particular, we suggest using the Ramsey forcing notion. In this new context, we demonstrate that the set of oracles separating NP and coNP is 'not small', and obtain similar results for the separation of PSPACE from PH along with the separation of NP from BQP. In a related set of results, we demonstrate that these classes are all of the same descriptive complexity. Finally we demonstrate that this strengthening of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here.

Cake and coffee will be served in GAB 472 following this event.