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.

    Download (220kB) | Preview
    Official URL:

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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
      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)

      View Item Item control page


      Downloads per month over past year

      Origin of downloads