We extend the lower bound techniques of [Fortnow], to the
unbounded-error probabilistic model. A key step in the argument
is a generalization of Nepomnjascii's theorem from the Boolean
setting to the arithmetic setting. This generalization is made
possible, due to the recent discovery of logspace-uniform TC^0
circuits for iterated multiplication.

Here is an example of the sort of lower bounds that we obtain:
we show that MajMajSAT is not contained in PrTiSp(n^{1+o(1)},n^e)
for any e < 1. We also extend a lower bound of [Fortnow], from
showing that co-SAT does not have uniform NC^1 circuits of
size n^{1+o(1)}, to a similar result for SAC^1 circuits.