Allender, Friedman, and Gasarch recently proved an upper bound of PSPACE for the class DTTR K of decidable languages that are polynomial-time truth-table reducible to the set of prefix-free Kolmogorov-random strings regardless of the universal machine used in the definition of Kolmogorov complexity. It is conjectured that DTTR K in fact lies closer to BPP , a lower bound established earlier by Buhrman, Fortnow, Koucký, and Loff. It is also conjectured that we have similar bounds for the analogous class DTTR C defined by plain Kolmogorov randomness. In this paper, we provide further evidence for these conjectures. First, we show that the time-bounded analogue of DTTR C sits between BPP and PSPACE ∩ P / poly . Next, we show that the class DTTR C , α obtained from DTTR C by imposing a super-constant minimum query length restriction on the reduction lies between BPP and PSPACE . Finally, we show that the class P / R C t = log obtained by further restricting the reduction to ask queries of logarithmic length lies between BPP and Σ 2 p ∩ P / poly .