Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin

Abstract

We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice (AMEXP/2nε) requires circuit complexity at least 2n/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 sub-exponential advice by Hirahara, Lu, and Ren (CCC’23). Our result is proved by combining the recent iterative win-win paradigm of Chen, Lu, Oliveira, Ren, and Santhanam (FOCS’23) together with the uniform hardness-vs-randomness connection for Arthur-Merlin protocols by Shaltiel-Umans (STOC’07) and van Melkebeek-Sdroievski (CCC’23). We also provide a conceptually different proof using a novel ”critical win-win” argument that extends a technique of Lu, Oliveira, and Santhanam (STOC’21). Indeed, our circuit lower bound is a corollary of a new explicit construction for properties in coAM. We show that for every dense property P ∈ coAM, there is a quasi-polynomial-time Arthur-Merlin protocol with short advice such that the following holds for infinitely many n: There exists a canonical string wn ∈ P ∩ {0,1}n so that (1) there is a strategy of Merlin such that Arthur outputs wn with probability 1 and (2) for any strategy of Merlin, with probability 2/3, Arthur outputs either wn or a failure symbol ⊥. As a direct consequence of this new explicit construction, our circuit lower bound also generalizes to circuits with an AM ∩ coAM oracle. To our knowledge, this is the first unconditional lower bound against a strong non-uniform class using a hard language that is only ”quantitatively harder”.