Amplifying lower bounds by means of self-reducibility

Eric Allender, Michal Koucký

Research output: Contribution to journalArticlepeer-review

65 Scopus citations


We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC0 circuits if and only if it has TC0 circuits of size n 1+ε for every ε > 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC1 and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC 0 circuits of size n1+εd. If one were able to improve this lower bound to show that there is some constant ε > 0 (independent of the depth d) such that every TC0 circuit family recognizing BFE has size at least n1+ε, then it would follow that TC 0≠NC1. We show that proving lower bounds of the form n1+ε is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC0, TC0 and NC1 via existing natural approaches to proving circuit lower bounds. We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC0 and AC 0[6] circuits of size n1+c for some constant c depending on d.

Original languageEnglish (US)
Article number14
JournalJournal of the ACM
Issue number3
StatePublished - Mar 1 2010

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Circuit complexity
  • Lower bounds
  • Natural proofs
  • Self-reducibility
  • Time-space tradeoffs


Dive into the research topics of 'Amplifying lower bounds by means of self-reducibility'. Together they form a unique fingerprint.

Cite this