Jin-Yi Cai (University of Wisconsin, Madison):
On Proving Circuit Lower Bounds Against PH: Positive and Negative Results
We consider the problem of proving circuit lower bounds against the polynomial-time hierarchy PH. We give both positive and negative results. For the positive side, for any fixed integer k, we give an explicit Sigma 2 language, that requires circuit size $>n^k$. Our main theorem is on the negative side. We give evidence that it is infeasible to give relativizable proofs that any single language in the polynomial-time hierarchy requires super polynomial circuit size. For this we introduce a stringent oracle access model. Our proof techniques are based on the decision tree version of the Switching Lemma for constant depth circuits and Nisan-Wigderson pseudorandom generator. We also give some inapproximability results on constant depth circuits with better constants in the exponents in the previously published lower bounds.
Joint work with Osamu Watanabe.