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

    [thumbnail of PM-ZPP-2002.pdf]
    Preview
    Text
    PM-ZPP-2002.pdf

    Download (207kB) | Preview

    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
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/8248
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only (login required)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads