We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.
Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ... more >>>

We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice ($AMEXP_{/2^{n^{\varepsilon}}}$) requires circuit complexity at least $2^n/n$. Previously, the best known such near-maximum lower bounds were for symmetric exponential time by Chen, Hirahara, and Ren (STOC'24) and Li (STOC'24), or randomized exponential time with MCSP oracle and ... more >>>