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 >>>