BPP has effective dimension at most 1/2 unless BPP=EXP
Philippe Moser · Maynooth University ePrints and eTheses Archive (Maynooth University) · 2003
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.