Time-space tradeoffs in the counting hierarchy

Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

We extend the lower bound techniques of [14], 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 [9]. 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 [14], from showing that SAT does not have uniform NC1 circuits of size n1+0(1), to a similar result for SAC1 circuits.

Original languageEnglish (US)
Pages (from-to)295-302
Number of pages8
JournalProceedings of the Annual IEEE Conference on Computational Complexity
DOIs
StatePublished - 2001

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Time-space tradeoffs in the counting hierarchy'. Together they form a unique fingerprint.

Cite this