We extend the lower bound techniques of , to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjaŝĉiî's theorem from the Boolean setting to the arithmetic setting. This generalization is made possible, due to the recent discovery of logspace-uniform TC0 circuits for iterated multiplication . Here is an example of the sort of lower bounds that we obtain: we show that MAJ·MAJSAT is not contained in PrTiSp(n1+0(1), nε) for any ε < 1. We also extended a lower bound of , from showing that SAT does not have uniform NC1 circuits of size n1+0(1), to a similar result for SAC1 circuits.
|Original language||English (US)|
|Number of pages||8|
|Journal||Proceedings of the Annual IEEE Conference on Computational Complexity|
|State||Published - 2001|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computational Mathematics