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

2026-07-10 • Computational Complexity

Computational Complexity

AI summaryⓘ

The authors prove that a certain complex class of problems involving exponential time, a special kind of probabilistic verification (promise-MA), and a small bit of extra information (one bit of advice) can't be solved by small logical circuits much smaller than about 2 to the power of n divided by n. They use a strategy called the iterative win-win paradigm, connect a specific problem (Range Avoidance) to circuit size limitations, and apply the PCP theorem, which is a fundamental result about checking proofs efficiently. An important part of their approach analyzes a computation model that makes a limited number of step-by-step NP queries with bounded witness lengths. Overall, their work sharpens our understanding of how hard it is to simulate these computations with circuits of certain sizes.

circuit lower boundscomplexity class E^prMAiterative win-win paradigmRange Avoidance problemPCP theorempromise-MA oracleP^NP with adaptive querieswitness lengthexponential timeadvice bits

Authors

Hanlin Ren, Ryan Williams

Abstract

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 promise-$\mathsf{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 (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{NP}$ with $r(n)$ adaptive rounds of $\mathsf{NP}$ queries, where each $\mathsf{NP}$ query has witness length $s(n)$.

View PDFOpen arXiv