{"id":"30039dc8-3c33-45bf-b1b7-a30812bacf9e","arxiv_id":"2607.09963","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"E^{prMA}/1 contains a language requiring circuits of size Ω(2^n/n).","lead":"The paper proves that exponential time with a promise-Merlin-Arthur oracle and one advice bit contains a function needing nearly the largest possible circuits (size about 2^n/n). This advances the long program of placing hard functions in weaker uniform classes, with tools that may reach even smaller classes.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript supplies complete, self-contained proofs for every lemma used by the main theorems; the only technical ingredients that could have been fragile (bounded-round computational history, systematic PCP, uniform reconstruction, parameter bookkeeping) are written out in full and check out under standard complexity-theoretic scrutiny. The reader correctly isolated the PCP/self-corrector interface as the most delicate step, yet that interface is verified rather than assumed. Consequently the ACCEPT / HIGH / low-risk assessment stands; no adjustment is warranted.","tokens_in":29511,"tokens_out":556,"duration_ms":17487,"concrete_test":"Independently re-derive the soundness direction of the final query q_pfx,i in the proof of Thm 4.1 (pp. 15–16) under the concrete field-size and degree bounds of Thm 3.5 (m = ⌈log t′ / log log t′⌉, |F| = Θ((m|H|)^{3}), δ = 1/4), confirming that self-corrector error after O(log t) repetitions remains < 1/4 while PCP soundness stays ≤ 1/2; if the combined rejection probability drops below 1/2 the smartness claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Thm 1.1 / 1.2) rests on the instance-wise hardness-randomness tradeoff of Thm 4.1 (Solve/Recon for AVOID via Jeřábek–Korten + systematic RM-PCP of Thm 3.5) feeding the iterative win-win of §4.2. The reader’s candidate weak point—the systematic Reed–Muller prefix of the PCP together with low-degree self-correction when circuit size ≤ O(k^{4} log T)—is handled carefully: completeness of Thm 3.5 supplies an exact polynomial whose self-correction succeeds with probability 1, soundness + amplification keeps Arthur’s rejection probability ≥ 1/2 on non-promise-violating NO instances, and the induction on pfx in the proof of Thm 4.1 shows every query stays inside the prMA promise precisely when Solve fails. Parameter choices (C > D, ri ≤ O(ni), Ti = ni+1 after i⋆) close the iteration without circularity or hidden non-uniformity. No internal inconsistency or unstated assumption that would falsify single-valued smart-FP^{prMA}/1 appears.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":29829,"tokens_out":823,"duration_ms":23401,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is already at the level expected for a top theory journal (STOC/FOCS/JACM/SICOMP). The technical core is carefully executed and the open questions in §5 are well-posed. I see no reason to delay acceptance for further technical work."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper puts a near-maximum hard function into E^{prMA}/1 (and smart-E^{prMA}/1). That is the real advance: it moves the state of the art for Merlin-Arthur-type classes past the half-exponential barrier that has sat there since BFT98 and Santhanam, and past the AMEXP/advice results of CLL25.\n\nWhat is new is the combination. They take the iterative win-win of CLO+23, feed it the Jeřábek–Korten reduction, and make the reconstruction work inside smart-FP^{prMA} by analyzing the intermediate class P^{NP}[#rounds=r, length=s]. Lemma 3.2 and Theorem 3.5 (encoded history via a systematic Reed–Muller PCP) are the original technical objects; Theorem 4.1 then gives an instance-wise hardness-randomness tradeoff whose reconstruction stays smart precisely when Solve fails. The parameter chase in §4.2 (C > D, n_{i+1}=n_i^C, r_i = O(n_i), T_i = n_{i+1} after i*) closes cleanly and produces the infinitely-often smart Avoidance algorithm of Theorems 1.2/4.5. The proofs are complete, the smartness invariant is maintained by induction, and the argument is non-circular.\n\nThe soft spots are minor and already flagged by the authors. The one-bit advice and the infinitely-often nature are real limitations; the discussion section is honest that the same method does not yet reach prMAE or MAEXP without stronger assumptions on search-to-decision for SAT. The reliance on the systematic RM prefix and low-degree self-correction is handled carefully in the proofs of 3.5 and 4.1, so the candidate weak point does not break single-valuedness. Citations are appropriate and the half-exponential relativizing appendix is a useful contrast.\n\nThis is for people who care about circuit lower bounds for MA-type classes, Range Avoidance, and uniform reconstruction. It deserves a serious referee. I would engage with it and expect to cite the Avoidance algorithm and the bounded-round machinery.","headline":"Solid near-maximum lower bound for E^{prMA}/1 via a carefully parameterized Avoidance solver; the technical core holds up.","tokens_in":30434,"tokens_out":546,"would_cite":true,"duration_ms":6185,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q17"],"pacs":[],"model":"grok-4.5","headline":"Exponential time with one bit of advice and a promise Merlin-Arthur oracle needs near-maximum circuit size.","keywords":["circuit lower bounds","Range Avoidance","Merlin-Arthur","promise problems","iterative win-win","PCP theorem","bounded-adaptive NP queries","hardness-randomness tradeoff"],"falsifier":"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.","tokens_in":30449,"feed_emoji":"⚡","tokens_out":1092,"duration_ms":10676,"temperature":0.7,"pith_summary":"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.","feed_headline":"Near-max circuit hardness for exp-time with MA queries","feed_subtitle":"One advice bit and a promise Merlin-Arthur oracle already force size 2^n/n","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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}"],"fun_headline_variants":["Near-max size 2^n/n circuits forced for E^{prMA}/1","E with prMA oracle and one advice bit hits near-max circuit hardness","Promise-MA queries yield Ω(2^n/n) circuit lower bounds in exp-time","Near-maximum circuit hardness for exponential time with MA queries","One advice bit plus prMA already demands circuits of size 2^n/n"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Near-max size 2^n/n circuits forced for E^{prMA}/1","E with prMA oracle and one advice bit hits near-max circuit hardness","Promise-MA queries yield Ω(2^n/n) circuit lower bounds in exp-time","Near-maximum circuit hardness for exponential time with MA queries","One advice bit plus prMA already demands circuits of size 2^n/n"]},"model":"grok-4.5","effort":"low","cost_usd":0.004278,"raw_usage":{"total_tokens":1269,"prompt_tokens":738,"num_sources_used":0,"completion_tokens":110,"cost_in_usd_ticks":42780000,"prompt_tokens_details":{"text_tokens":738,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":421,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":738,"tokens_out":110,"duration_ms":4853,"temperature":1.0,"reasoning_tokens":421,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T14:16:24.941716+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}