Amplifying circuit lower bounds against polynomial time, with applications

We give a self-reduction for the Circuit Evaluation problem (CircEval) and prove the following consequences. Amplifying size-depth lower bounds. If CircEval has Boolean circuits of n(k) size and n(1-delta) depth for some k and delta, then for every epsilon > 0, there is a delta' > 0 such that CircEval has circuits of n(1+epsilon) size and n(1-delta') depth. Moreover, the resulting circuits require only (O) over tilde (n(epsilon)) bits of non-uniformity to construct. As a consequence, strong enough depth lower bounds for Circuit Evaluation imply a full separation of P and NC (even with a weak size lower bound). Lower bounds for quantified Boolean formulas. Let c, d > 1 and e < 1 satisfy c < (1 - e + d)/d. Either the problem of recognizing valid quantified Boolean formulas (QBF) is not solvable in TIME[n(c)], or the Circuit Evaluation problem cannot be solved with circuits of n(d) size and n(e) depth. This implies unconditional polynomial-time uniform circuit lower bounds for solving QBF. We also prove that QBF does not have n(c)-time uniform NC circuits, for all c < 2.