ECCC-Report TR03-029https://eccc.weizmann.ac.il/report/2003/029Comments and Revisions published for TR03-029en-usWed, 23 Apr 2003 20:57:34 +0300
Paper TR03-029
| BPP has effective dimension at most 1/2 unless BPP=EXP |
Philippe Moser
https://eccc.weizmann.ac.il/report/2003/029 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.
Wed, 23 Apr 2003 20:57:34 +0300https://eccc.weizmann.ac.il/report/2003/029