Bootstrapping results for threshold circuits “just beyond” known lower bounds
Lijie Chen, Roei Tell · 2019
The best known lower bounds for the circuit class TC0 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 TC0. Specifically: