Chang, RichardRohatgi, Pankaj2007-04-232007-04-231990-10http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1154https://hdl.handle.net/1813/6994We investigate random reductions from complete sets in the Boolean Hierarchy to their complements. We show that under the assumption that the Polynomial Hierarchy is infinite, the error probability of such reductions cannot be significantly lower than a constant. This constant depends on the classes in question. Thus, random reductions in the Boolean Hierarchy are not robust. We also show that the trivial random reductions between classes at the second level of the Boolean Hierarchy are optimal.1458520 bytes314096 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report