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 nk size and n1−δ depth for some k and δ, then for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\epsilon > 0}$$\end{document}, there is a δ′ > 0 such that CircEval has circuits of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n^{1 + \epsilon}}$$\end{document} size and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n^{1- \delta^{\prime}}}$$\end{document} depth. Moreover, the resulting circuits require only \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\tilde{O}(n^{\epsilon})}$$\end{document} 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[nc], or the Circuit Evaluation problem cannot be solved with circuits of nd size and ne depth. This implies unconditional polynomial-time uniform circuit lower bounds for solving QBF. We also prove that QBF does not have nc-time uniform NC circuits, for all c < 2.