We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for all real numbers 1 ≤ α < β, BPTIME(n^(α)/1 ⊊ BPTIME(n^(β)/1. This result builds on and improves an earlier hierarchy of Barak using 0(log log n) bits of advice.

We also show that for any constant d > 0, there is a language L computable on average in BPP but not on average in BPTIME(n^(d)).

We build on Barak's techniques by using a different translation argument and by a careful application of the fact that there is a PSPACE-complete problem L such that worst-case probablistic algorithms for L take only slightly more time thane average-case algorithms.