MURAL - Maynooth University Research Archive Library



    ZPP is Hard Unless RP is Small


    Moser, Philippe (2002) ZPP is Hard Unless RP is Small. Electronic Colloquium on Computational Complexity (15). ISSN 1433-8092

    [img]
    Preview
    Download (207kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We use Lutz's resource bounded measure theory to prove that, either RP is small, or ZPP is hard. More precisely, we prove that if RP has not p-measure zero, then EXP equals ZPP on infinitely many input lengths, i.e. there are infinitely many input lengths on which ZPP is hard. Second we prove that if NP has not p-measure zero, then derandomization of AM is possible on infinitely many input length, i.e. there are infinitely many input lengths such that NP = AM. Finally we prove easiness versus randomness tradeoffs for classes in the polynomial time hierarchy. We show that it appears to every strong adversary that either, every Ʃᴾᵢ algorithm can be simulated infinitely often by a subexponential co-nondeterministic time algorithm, having oracle access to Ʃᴾᵢ -2 , or BP Ʃᴾᵢ = Ʃᴾᵢ .

    Item Type: Article
    Keywords: derandomization; ZPP; RP;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 8248
    Depositing User: Philippe Moser
    Date Deposited: 29 May 2017 14:33
    Journal or Publication Title: Electronic Colloquium on Computational Complexity
    Publisher: Weizmann Institute of Science
    Refereed: No
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year