Uniform derandomization from pathetic lower bounds

A recurring theme in the literature on derandomization is that probabilistic algorithms can be simulated quickly by deterministic algorithms, if one can obtain impressive (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is needed for derandomization, existing lower bounds seem rather pathetic (linear-size lower bounds for general circuits [30], nearly cubic lower bounds for formula size [23], nearly nloglogn size lower bounds for branching programs [12], n ^1+cd for depth d threshold circuits [26]). Here, we present two instances where "pathetic" lower bounds of the form n ^1+ε would suffice to derandomize interesting classes of probabilistic algorithms. We show: - If the word problem over S₅ requires constant-depth threshold circuits of size n^1+ε for some ε>0, then any language accepted by uniform polynomial-size probabilistic threshold circuits can be solved in subexponential time (and more strongly, can be accepted by a uniform family of deterministic constant-depth threshold circuits of subexponential size.) - If no constant-depth arithmetic circuits of size n^1+ε can multiply a sequence of n 3-by-3 matrices, then for every constant d, black-box identity testing for depth-d arithmetic circuits with bounded individual degree can be performed in subexponential time (and even by a uniform family of deterministic constant-depth AC⁰ circuits of subexponential size).