Amplifying lower bounds by means of self-reducibility

We observe that many important computational problems in NC¹ share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC⁰ circuits if and only if it has TC⁰ 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 NC¹ and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC ⁰ circuits of size n₁₊ε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 TC⁰ circuit family recognizing BFE has size at least n^1+ε, then it would follow that TC ⁰≠NC¹. We show that proving lower bounds of the form n^1+ε 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 ACC⁰, TC⁰ and NC¹ 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 TC⁰ and AC ⁰[6] circuits of size n^1+c for some constant c depending on d.