Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering strong separations, witnessed by immune languages.

The main result of the paper shows that with respect to a random oracle the levels of the polynomial ... more >>>