ECCC-Report TR01-041https://eccc.weizmann.ac.il/report/2001/041Comments and Revisions published for TR01-041en-usWed, 30 May 2001 17:55:31 +0300
Paper TR01-041
| Time-Space Tradeoffs in the Counting Hierarchy |
Eric Allender,
Michal Koucky,
Detlef Ronneburger,
Sambuddha Roy,
V Vinay
https://eccc.weizmann.ac.il/report/2001/041We 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.
Wed, 30 May 2001 17:55:31 +0300https://eccc.weizmann.ac.il/report/2001/041