We prove a near-maximum ($2^n / n$) circuit lower bound for the complexity class $\mathrm{E}^{\mathrm{prMA}}/_1$, corresponding to exponential time with access to a promise-$\mathrm{MA}$ 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 (Jerabek, Ann. Pure Appl. Log. '04; Korten, FOCS'21), and the PCP theorem. Crucial to our proof is the analysis of the complexity class $\mathrm{P}^\mathrm{NP}[\textrm{#rounds}=r, \textrm{length}=s]$, which is $\mathrm{P}^\mathrm{NP}$ with $r(n)$ adaptive rounds of $\mathrm{NP}$ queries, where each $\mathrm{NP}$ query has witness length $s(n)$.

Fix broken links in the pdf

We prove a near-maximum ($2^n / n$) circuit lower bound for the complexity class $\mathrm{E}^{\mathrm{prMA}}/_1$, corresponding to exponential time with access to a promise-$\mathrm{MA}$ 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 (Jerabek, Ann. Pure Appl. Log. '04; Korten, FOCS'21), and the PCP theorem. Crucial to our proof is the analysis of the complexity class $\mathrm{P}^\mathrm{NP}[\textrm{#rounds}=r, \textrm{length}=s]$, which is $\mathrm{P}^\mathrm{NP}$ with $r(n)$ adaptive rounds of $\mathrm{NP}$ queries, where each $\mathrm{NP}$ query has witness length $s(n)$.