Show simple item record

dc.contributor.authorChang, Richarden_US
dc.contributor.authorRohatgi, Pankajen_US
dc.date.accessioned2007-04-23T17:49:41Z
dc.date.available2007-04-23T17:49:41Z
dc.date.issued1990-10en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1154en_US
dc.identifier.urihttps://hdl.handle.net/1813/6994
dc.description.abstractWe 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.en_US
dc.format.extent1458520 bytes
dc.format.extent314096 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleRandom Reductions in the Boolean Hierarchy are Not Robust.en_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics