Abstract:
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.