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

Hanlin Ren, Ryan Williams

We prove a near-maximum ($2^n/n$) circuit lower bound for the complexity class ${\mathsf{E}}^{\mathrm{pr}\mathsf{MA}}{/}_1$, corresponding to exponential time with access to a promis…