Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries

We prove a near-maximum ($2^n\mathrm{/}n$) circuit lower bound for the complexity class ${\mathsf{E}}^{\mathrm{p}\mathrm{r}\mathsf{M}\mathsf{A}}{\mathrm{/}}_1$, corresponding to exponential time with access to a promise-$\mathsf{M}\mathsf{A}$ oracle and one bit of advice. Our proof incorporates the iterative win-win paradigm (Chen–Lu–Oliveira–Ren–Santhanam, FOCS’23), the reduction from the Range Avoidance problem to circuit lower bounds (Jeřábek, Ann. Pure Appl. Log. '04; Korten, FOCS’21), and the PCP theorem. Crucial to our proof is the analysis of the complexity class \mathsf{P}^\mathsf{NP}[{\textsf{#rounds}}=r, {\textsf{length}}=s], which is ${\mathsf{P}}^{\mathsf{N}\mathsf{P}}$ with $r(n)$ adaptive rounds of $\mathsf{N}\mathsf{P}$ queries, where each $\mathsf{N}\mathsf{P}$ query has witness length $s(n)$.