Share and Export
Share and Export
Moser, Philippe (2003) BPP has effective dimension at most 1/2 unless BPP=EXP. Technical Report. Electronic Colloquium on Computational Complexity.
Preview
PM-BPP-2003.pdf
Download (220kB) | Preview
Official URL: https://eccc.weizmann.ac.il/report/2003/029/
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: | https://mural.maynoothuniversity.ie/id/eprint/10311 |
| 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
Downloads
Downloads per month over past year
