Pith. sign in

REVIEW 5 minor 9 references

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

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Exponential time with one bit of advice and a promise Merlin-Arthur oracle needs near-maximum circuit size.

desk verdict Solid near-maximum lower bound for E^{prMA}/1 via a carefully parameterized Avoidance solver; the technical core holds up. read the letter →

arxiv 2607.09963 v1 pith:MEPCKAWM submitted 2026-07-10 cs.CC

Hanlin Ren , Ryan Williams This is my paper · ORCID
classification cs.CC MSC 68Q1568Q17
keywords circuitlowerboundsRangeAvoidanceMerlin-Arthurpromiseproblemsiterativewin-winPCPtheorembounded-adaptiveNPquerieshardness-randomnesstradeoff
topics P versus NP
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that some language computable in exponential time with a promise Merlin-Arthur oracle and a single advice bit requires circuits of size roughly 2^n/n. That size is essentially the largest possible: almost every function needs circuits that large, yet until now the best uniform classes known to contain such functions sat higher in the hierarchy. The argument works by solving the Range Avoidance problem—given a circuit that maps n bits to n+1 bits, find a string outside its range—using an iterative win-win that either finds a hard truth table directly or reconstructs an earlier hard history via smart promise-MA queries. Because the reconstruction only ever queries instances that satisfy the promise, the algorithm is single-valued and the lower bound holds for a clean complexity class. A sympathetic reader cares because near-maximum hardness is the quantitative strength needed for many derandomization and cryptography applications, and the result moves that hardness into a class already known to admit weaker circuit lower bounds.

What carries the argument

The instance-wise hardness-randomness tradeoff for Range Avoidance (Theorem 4.1): a multi-output function f computed by a P^NP machine with a bounded number of adaptive short-witness rounds either solves Avoid via the Jeřábek–Korten reduction, or admits a smart polynomial-time reconstruction of every bit of f by successive promise-MA queries that recover the lexicographically largest short history prefix of a systematic Reed–Muller PCP.

What would settle it

Exhibit a polynomial-size circuit family C_n:{0,1}^n→{0,1}^{n+1} such that every smart FP^{prMA}/1 procedure either errs on infinitely many n or makes a non-promise query on every purported good length produced by the iterative construction of Section 4.2.

Watch

Extended reading notes

Core claim

There is a language in smart-E^{prMA}/1 that requires Boolean circuits of size Ω(2^n/n). Equivalently, there is an infinitely-often smart FP^{prMA}/1 algorithm that, given any polynomial-size circuit C:{0,1}^n → {0,1}^{n+1}, outputs a string outside the range of C.

Load-bearing premise

The reconstruction works only if the systematic Reed–Muller PCP of the bounded-round history preserves the lexicographically largest short prefix and the low-degree self-corrector succeeds whenever that history has small circuits; if either fails for the parameters used in the win-win, the queries leave the promise and single-valuedness collapses.

Editorial extensions

If this is right

  • smart-E^{prMA}/1 is not contained in SIZE[2^n/n]
  • the same class contains languages that cannot be approximated by size-2^{δ_1 n} circuits better than 1/2+2^{-δ_2 n} for δ_1+2δ_2<1
  • smart-E^{prMA}/1 is not contained in TIME[2^{kn}]/2^{n-α(n)} for any constant k and α(n)→∞
  • the Avoid algorithm yields smart-FP^{prMA}/1 constructions of Ramsey graphs, two-source extractors, rigid matrices and GV-optimal codes on infinitely many lengths
  • if search-SAT admits non-adaptive NP queries then the same near-maximum lower bound holds already for smart-E^{prMA}[2^{εn}]/1 and for (MAE∩coMAE)/2^{εn}

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same iterative reconstruction template may be adaptable to other total search problems whose hardness-randomness tradeoffs use only a logarithmic number of adaptive short-witness NP rounds, potentially placing near-maximum hardness into still smaller interactive classes.
  • Because the advice bit merely signals which input lengths are good, any future derandomization of the reconstruction that eliminates that bit would immediately give a fully uniform near-maximum lower bound for smart-E^{prMA}.
  • The half-exponential relativizing lower bound recorded in the appendix shows that the non-relativizing PCP ingredient is essential for crossing from half-exponential to near-maximum size.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper proves that the class E^{prMA}/1 contains a language requiring Boolean circuits of size Ω(2^n/n). Equivalently, it constructs an infinitely-often smart-FP^{prMA}/1 algorithm for the Range Avoidance problem on every polynomial-size circuit C:{0,1}^n→{0,1}^{n+1}. The argument combines the iterative win-win paradigm of Chen–Lu–Oliveira–Ren–Santhanam, the Jeřábek–Korten reduction from Avoidance to hard truth tables (with an explicit bound on adaptive NP-query rounds and witness length), and a systematic Reed–Muller PCP that yields an encoded computational history for the restricted class P^{NP}[#rounds=r, length=s]. A uniform reconstruction procedure running in smart-P^{prMA} closes the win-win, and a single advice bit selects the good input lengths on which the solver succeeds.

Significance. If correct, the result is a substantial advance in uniform circuit lower bounds: it moves near-maximum hardness from S_2E / E^{prAM} down to exponential time with a promise-Merlin–Arthur oracle and only one bit of advice, while preserving smartness (hence single-valuedness). The technical development of bounded-round, short-witness P^{NP} and the instance-wise hardness-randomness tradeoff with uniform smart-prMA reconstruction are of independent interest and open a plausible route toward still smaller classes (e.g., prMAE). The proofs are self-contained from standard ingredients (PCP, low-degree self-correction, counting) with carefully tracked parameters and no circularity.

minor comments (5)
  1. In §4.2 the constant C is first required to be ≥3 and later required to satisfy C>D+1; a single sentence fixing the order of quantifiers (choose D from the running-time exponent of Solve, then choose C>max{D+1,3}) would remove a minor presentational ambiguity.
  2. Theorem 3.4 is labelled “Proof Sketch” and relies on a specific robust PCP from Harsha’s thesis. For archival completeness it would help to state the precise parameter settings (field size, degree, soundness amplification) that are used later in the self-corrector of Theorem 4.1, even if the full PCP construction is only cited.
  3. The composition of the smart-FP^{prMA}/1 solver for truth-table generators (Theorem 4.3) with Korten’s FP^{NP} reduction (Lemma 4.4) is correct because NP⊆ MA, but a one-sentence remark that every NP query is automatically inside the prMA promise would make the smartness claim of Theorem 4.5 fully explicit.
  4. Notation for the restricted class P^{NP}[#rounds=r, length=s] is introduced cleanly, yet a short table or display of the successive (r_i,s_i,T_i) recurrences in §4.2 would aid readers tracking the iteration.
  5. A few minor typos appear (e.g., “Jeˇrábek–Korten” spacing, “pr MA” vs “prMA”). A final pass for consistency of oracle notation would be welcome.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is a self-contained constructive proof from standard PCP, self-correction, and Jeřábek–Korten ingredients.

full rationale

The derivation chain is: (i) Jeřábek–Korten (Thm 3.1) reduces AVOID to a hard truth table with bounded adaptive NP rounds; (ii) encoded computational history of the bounded-round class via a systematic Reed–Muller PCP (Lem 3.2 + Thm 3.5); (iii) instance-wise hardness-randomness tradeoff with uniform smart-prMA reconstruction (Thm 4.1); (iv) iterative win-win over a sequence of AVOID instances (Thm 4.3 / §4.2) that eventually yields an infinitely-often smart-FP^{prMA}/1 AVOID solver, hence the near-maximum lower bound (Thm 1.1 / Cor 4.6). None of these steps is definitional of the conclusion: the hard function is explicitly constructed by the solver rather than assumed; parameters (C > D, r_i ≤ O(n_i), T_i = n_{i+1} after i★) are chosen to close the iteration without fitting data; self-citations (CLO+23 win-win, Jeřábek/Korten, classical PCP) are used as black-box tools whose statements are restated and proved or cited with independent external proofs. Completeness of the PCP supplies an exact low-degree polynomial so self-correction succeeds with probability 1 on YES instances; soundness + induction on the prefix keep every Recon query inside the prMA promise precisely when Solve fails. There are no fitted parameters renamed as predictions, no uniqueness theorems imported from the authors that force the result, and no renaming of a known empirical pattern. The argument is therefore self-contained against external complexity benchmarks and scores 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper rests on standard complexity-theoretic primitives (PCP theorem of Arora et al., low-degree self-correction, Jeřábek–Korten reduction, iterative win-win template) plus one new technical definition (bounded-round P^{NP}). No numerical free parameters are fitted; all constants are chosen large enough for asymptotic inequalities. The only invented entity is the restricted query class itself, introduced solely as a bookkeeping device.

assumptions (4)
  • standard math Classical PCP theorem for Circuit-SAT with systematic Reed-Muller encoding and robust soundness (Theorem 3.4, citing AS98/ALM+98/Har04).
    Used to obtain the encoded computational history of bounded-round P^{NP} machines; completeness and soundness are invoked verbatim in Theorem 3.5 and the reconstruction of Theorem 4.1.
  • standard math Low-degree self-corrector for polynomials of total degree Δ over fields of size ω(Δ^{2}) (Theorem 2.3, GS92/Sud95).
    Invoked inside every prMA query of Recon to recover bits of the closest low-degree polynomial; success probability 2/3 is amplified by repetition.
  • domain assumption Jeřábek–Korten reduction from Avoidance to hard truth tables, re-analyzed for round complexity O(n+log T) and witness length n (Theorem 3.1).
    Core hardness-randomness tradeoff; the paper supplies a self-contained proof optimizing the number of adaptive rounds.
  • domain assumption Iterative win-win template of CLO+23 adapted to single-valued smart-FP^{prMA} solvers.
    High-level structure of Section 4.2; the paper supplies the concrete hardness-randomness tradeoff that makes the template work for Avoidance.
invented entities (1)
  • P^{NP}[#rounds=r(n), length=s(n)]
    purpose: Bookkeeping class that tracks the exact adaptive-round and witness-length resources of the Jeřábek–Korten procedure and of the encoded history, enabling the reconstruction to stay inside smart-FP^{prMA}.
    Defined in Section 3; used throughout Lemmas 3.2 and Theorems 3.5/4.1. No independent physical or computational existence claimed beyond its definitional role.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries." pith.science (2026). https://pith.science/paper/MEPCKAWM

@misc{pith2026260709963,
  author       = {Pith},
  title        = {Pith review of: Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MEPCKAWM}},
  note         = {Machine review of arXiv:2607.09963}
}
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\v{r}\'abek, 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)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

9 extracted references

  1. [1]

    Derandomizing Arthur- Merlin games and approximate counting implies exponential-size lower bounds

    [AGHK11] Barı¸ s Aydınlıo˘ glu, Dan Gutfreund, John M. Hitchcock, and Akinori Kawachi. “Derandomizing Arthur- Merlin games and approximate counting implies exponential-size lower bounds”. In: Comput. Com- plex. 20.2 (2011), pp. 329–366 (cit. on p. 2). [AK01] Vikraman Arvind and Johannes Köbler. “On pseudorandomness and resource-bounded measure”. In: Theor...

    2011

  2. [2]

    Symmetric exponential time requires near-maximum circuit size

    2023, pp. 1058–1066 (cit. on p. 2). [CHLR26] Lijie Chen, Shuichi Hirahara, Zeyong Li, and Hanlin Ren. “Symmetric exponential time requires near-maximum circuit size”. In: J. ACM 73.1 (Feb. 2026). ISSN : 0004-5411 (cit. on pp. 1, 19, 20). 21 [CHR24] Lijie Chen, Shuichi Hirahara, and Hanlin Ren. “Symmetric exponential time requires near-maximum circuit size...

    2023

  3. [3]

    Maximum circuit lower bounds for exponential-time Arthur Merlin

    ACM, 2024, pp. 620–629 (cit. on p. 2). [CLL25] Lijie Chen, Jiatu Li, and Jingxun Liang. “Maximum circuit lower bounds for exponential-time Arthur Merlin”. In: STOC. ACM, 2025, pp. 1348–1358 (cit. on pp. 1, 2). [CLO+23] Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam. “Polynomial-time pseu- dodeterministic construction of primes”...

    2024

  4. [4]

    On promise problems: A survey

    LIPIcs. 2022, 20:1–20:21 (cit. on pp. 2, 19). [Gol06] Oded Goldreich. “On promise problems: A survey”. In: Essays in Memory of Shimon Even . Lecture Notes in Computer Science. Springer, 2006, pp. 254–290 (cit. on p. 2). [GS88] Joachim Grollmann and Alan L. Selman. “Complexity measures for public-key cryptosystems”. In: SIAM J. Comput. 17.2 (1988), pp. 309...

    2022

  5. [5]

    Highly resilient correctors for polynomials

    Lecture Notes in Computer Science. Springer, 1989, pp. 108– 118 (cit. on p. 8). [GS92] Peter Gemmell and Madhu Sudan. “Highly resilient correctors for polynomials”. In: Inf. Process. Lett. 43.4 (1992), pp. 169–174 (cit. on p. 7). [GZ11] Oded Goldreich and David Zuckerman. “Another proof that BPP ⊆ PH (and more)”. In: Studies in Complexity and Cryptography...

    1989

  6. [6]

    In search of an easy witness: expo- nential time vs. probabilistic polynomial time

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 244–263 (cit. on pp. 5, 9). [IKW02] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. “In search of an easy witness: expo- nential time vs. probabilistic polynomial time”. In: J. Comput. Syst. Sci. 65.4 (2002), pp. 672–694 (cit. on p. 1). 22 [ILW23] Rahul Ilango, Jiatu Li, and ...

    2015

  7. [7]

    P = BPP if E requires exponential circuits: derandomizing the XOR lemma

    ACM, 2023, pp. 1076–1089 (cit. on p. 2). [IW97] Russell Impagliazzo and Avi Wigderson. “ P = BPP if E requires exponential circuits: derandomizing the XOR lemma”. In: STOC. ACM, 1997, pp. 220–229 (cit. on pp. 1, 3, 4). [Jeˇ r04] Emil Jeˇ rábek. “Dual weak pigeonhole principle, Boolean complexity, and derandomization”. In: Ann. Pure Appl. Log. 129.1-3 (200...

    2023

  8. [8]

    Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma

    Lecture Notes in Computer Science. Springer, 1999, pp. 210–220 (cit. on pp. 1, 5). [MW20] Cody D. Murray and R. Ryan Williams. “Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma”. In: SIAM J. Comput. 49.5 (2020) (cit. on p. 1). [NW94] Noam Nisan and Avi Wigderson. “Hardness vs randomness”. In: J. Comput. Syst. Sci. 49....

    1999

Show all 9 references
  1. [9]

    NP is as easy as detecting unique solutions

    ISBN : 3-540-60615-7 (cit. on p. 7). 23 [VV86] Leslie G. Valiant and Vijay V . Vazirani. “ NP is as easy as detecting unique solutions”. In: Theor. Com- put. Sci. 47.3 (1986), pp. 85–93 (cit. on p. 20). [ZF87] Stathis Zachos and Martin Fürer. “Probabilistic quantifiers vs. dis...

    1986

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.