The best-known lower bounds for the circuit class \mathcal{TC}^0 are only slightly super-linear. Similarly, the best-known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative improvements of either of the two foregoing results would already imply super-polynomial lower bounds for \mathcal{TC}^0. Specifically:
1. If for every c>1 and sufficiently large d\in\mathbb{N} it holds that n-bit \mathcal{TC}^0 circuits of depth d require n^{1+c^{-d}} wires to compute certain \mathcal{NC}^1-complete functions, then \mathcal{TC}^0\ne\mathcal{NC}^1. In fact, even lower bounds for \mathcal{TC}^0 circuits of size n^{1+c^{-d}} against these functions when c>1 is fixed and sufficiently small would yield lower bounds for polynomial-sized circuits. Lower bounds of the form n^{1+c^{-d}} against these functions are already known, but for a fixed c\approx2.41 that is too large to yield new lower bounds via our results.
2. If there exists a deterministic algorithm that gets as input an n-bit \mathcal{TC}^0 circuit of depth d and n^{1+(1.61)^{-d}} wires, runs in time 2^{n^{o(1)}}, and distinguishes circuits that accept at most B(n)=2^{n^{1-(1.61)^{-d}}} inputs from circuits that reject at most B(n) inputs, then \mathcal{NEXP}\not\subseteq\mathcal{TC}^0. An algorithm for this ``quantified derandomization'' task is already known, but it works only when the number of wires is n^{1+c^{-d}}, for c>30, and with a smaller B(n)\approx2^{n^{1-(30/c)^{d}}}.
Intuitively, the ``takeaway'' message from our work is that the gap between currently-known results and results that would suffice to get super-polynomial lower bounds for \mathcal{TC}^0 boils down to the precise constant c>1 in the bound n^{1+c^{-d}} on the number of wires. Our results improve previous results of Allender and Kouck\'y (2010) and of the second author (2018), respectively, whose hypotheses referred to circuits with n^{1+c/d} wires (rather than n^{1+c^{-d}} wires). We also prove results similar to two results above for other circuit classes (i.e., \mathcal{ACC}^0 and \mathcal{CC}^0).
