TR01-041 Authors: Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay

Publication: 30th May 2001 17:55

Downloads: 854

Keywords:

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.