MURAL - Maynooth University Research Archive Library



    BPP has effective dimension at most 1/2 unless BPP=EXP


    Moser, Philippe (2003) BPP has effective dimension at most 1/2 unless BPP=EXP. Technical Report. Electronic Colloquium on Computational Complexity.

    [img]
    Preview
    Download (220kB) | Preview
    Official URL: https://eccc.weizmann.ac.il/report/2003/029/


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP. Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP on infinitely many input lengths. We also prove that BPP has measure zero in the smaller complexity class SUBEXP unless MA=EXP. Finally we show that under the plausible assumption Dtime (2^{dn}) is hard to approximate by sat-oracle circuits of size q (for every fixed polynomial q) bpp has p-dimension zero.

    Item Type: Monograph (Technical Report)
    Keywords: derandomization; resource bounded dimension; resource bounded measure;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 10311
    Identification Number: TR03-029
    Depositing User: Philippe Moser
    Date Deposited: 11 Dec 2018 16:50
    Publisher: Electronic Colloquium on Computational Complexity
    URI:

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year