Some Results on Circuit Lower Bounds and Derandomization of Arthur-Merlin Problems

Abstract

We prove a downward separation for ${\mathsf{\Sigma }}_2$-time classes. Specifically, we prove that if ${\Sigma }_2$E does not have polynomial size non-deterministic circuits, then ${\Sigma }_2$SubEXP does not have \textit{fixed} polynomial size non-deterministic circuits. To achieve this result, we use Santhanam's technique on augmented Arthur-Merlin protocols defined by Aydinlioğlu and van Melkebeek. We show that augmented Arthur-Merlin protocols with one bit of advice do not have fixed polynomial size non-deterministic circuits. We also prove a weak unconditional derandomization of a certain type of promise Arthur-Merlin protocols. Using Williams' easy hitting set technique, we show that ${\Sigma }_2$-promise AM problems can be decided in ${\Sigma }_2$SubEXP with $n^c$ advice, for some fixed constant $c$.