Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-029 | 1st April 2003 00:00

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

RSS-Feed




TR03-029
Authors: Philippe Moser
Publication: 23rd April 2003 20:57
Downloads: 1761
Keywords: 


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.



ISSN 1433-8092 | Imprint