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 n log log n size lower bounds for branching programs [12], n~(1+c_d) 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_5 requires constant-depth threshold circuits of size n_(1+∈) for some e > 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~0 circuits of subexponential size). Derandomization, Circuit Complexity, Polynomial Identity Testing