{"id":"aa078425-a29c-4a90-88a1-dda09ba3a07a","arxiv_id":"2607.08303","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"AC0 admits quasipolynomial-time learning under Gibbs measures with efficient local samplers, covering hard-core and Ising models on arbitrary bounded-degree graphs near sampling thresholds.","lead":"The paper gives a quasipolynomial-time algorithm that learns constant-depth AC0 circuits from samples of Gibbs distributions that admit efficient local samplers, without needing polynomial ball growth. This extends classical Fourier learning to many correlated spin systems on general bounded-degree graphs near their sampling thresholds.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader’s strongest claim accurately captures Theorems 5.7 and 1.1–1.3. The weakest-assumption diagnosis is also correct: everything funnels through Condition 5.6. After checking the constructions, the exponential-decay proofs appear to close the argument inside the stated regimes; the only remaining uncertainties are routine combinatorial bookkeeping. Consequently no load-bearing objection arises that would move the verdict away from ACCEPT. The concrete test simply re-verifies the single most delicate numerical inequality in the soft-constraint case; if it holds, confidence rises further without changing the decision.","tokens_in":40569,"tokens_out":525,"duration_ms":22062,"concrete_test":"Independently re-derive the soft-constraint drift bound in the proof of Lemma 6.3: verify that E[Zk|Fk-1]≤(1-η)/(1+η)+η/2≤1-η/2 with the chosen K=⌈log(2Δ/η)/log(2/(1-η))⌉, and that the resulting Azuma exponent yields α=exp(-η^{2}/(640K^{3}Δ^{3})). If the inequality fails for any fixed Δ≥2, η∈(0,1), the bi-directional sampler condition collapses for soft models.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 5.7) rests on Condition 5.6, which the reader correctly flags as the weakest assumption. That condition is not left abstract: Lemmas 6.1 and 6.3 construct explicit finite-state automata for the hard-core and soft-constraint regimes and prove the exponential tail via a fresh-call branching process dominated by a negative-drift martingale (Hoeffding/Azuma). The truncation-to-low-degree transfer (Lemmas 5.12–5.14) and the product-space Fourier extension (Theorem 4.2) are self-contained. Residual risks are ordinary constant-factor slips in the Azuma parameters or alphabet-size bookkeeping, not structural gaps that would invalidate the reduction. Outside the stated parameter regimes the exponential decay may fail, but the paper never claims those regimes.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper shows that if a bounded-degree Gibbs distribution admits a bi-directional (B,C,α)-good local sampler for systematic-scan Glauber dynamics (and its reverse), then every AC(d,n^c) function admits an L2 approximation of degree log^{O(d)}(n/ε) under that measure (Theorem 5.7). The construction realizes Samp as T-step systematic-scan Glauber driven by product marks, InvSamp via reverse heat-bath trajectories, and approximates both by truncating local automata (AppSamp/AppInvSamp). Determining mark sequences (Definition 5.8, Lemma 5.11) close the gap between fixed and stationary initialization; a product-space Fourier extension (Theorem 4.2) supplies the low-degree approximant on marks, which is transferred back by approximate inversion (Lemmas 5.10–5.14). Applications verify the sampler condition for hard-core with λ<(1-η)/(Δ-1) and soft-constraint two-spin systems with Ae≥1-(1-η)/(2Δ), including near-critical Ising, on arbitrary bounded-degree graphs (Theorems 1.1–1.3, Lemmas 6.1, 6.3).","tokens_in":40768,"tokens_out":882,"duration_ms":8129,"significance":"The result removes the polynomial-growth hypothesis of CGMV26 while retaining quasipolynomial learning for AC0 under genuinely dependent Gibbs measures on general bounded-degree graphs (expanders, ER graphs). The local-sampler abstraction cleanly connects LCA-style sampling to Fourier learning and is instantiated near classical Dobrushin/SSM thresholds (only a constant-factor gap). Strengths include an explicit reduction chain with error-budget lemmas, a self-contained product-domain Fourier tail (selector reduction + Tal), and concrete automata plus negative-drift branching-process analyses for the applications. If correct, this is a substantial advance in learning under correlated distributions.","major_comments":[{"comment":"No load-bearing gaps identified. Condition 5.6 is the weakest hypothesis, but Lemmas 6.1 and 6.3 construct explicit automata and prove exponential tails via fresh-call branching processes dominated by negative-drift martingales (Hoeffding/Azuma); the truncation and transfer lemmas (5.12–5.14) close the error budget with explicit parameter choices. Residual risks are ordinary constant-factor slips in Azuma parameters or alphabet bookkeeping, not structural failures of the reduction.","section":null}],"minor_comments":[{"comment":"Abstract and introduction cite CGMV as arXiv 2026 and the present paper as arXiv:2607.08303; these future-dated identifiers should be normalized for journal production.","section":null},{"comment":"Section 4: the selector-reduction argument is clear, but a one-line comparison of coordinate degree (codeg) to real multilinear degree when Q=2 would help readers coming from the Boolean setting.","section":null},{"comment":"Section 6.2: the soft-constraint mark alphabet size Q=12^{K(Δ+1)} is correct but large; a short remark that only the existence of a finite Q (independent of n) is used would clarify that the constant is not optimized.","section":null},{"comment":"Notation: Last(v,t) and the cyclic scan u are introduced in several places; a single preliminary definition would reduce repetition.","section":null},{"comment":"Acknowledgments note LLM assistance for Section 4; this is fine, but the journal may want a standard disclosure sentence.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is technically dense but the reduction is carefully modular. I see no novelty or citation issues relative to CGMV26; the local-sampler route is a genuine alternative to the SSM+polynomial-growth route. Fit for a theory venue is strong."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper does what it claims. CGMV26 needed strong spatial mixing plus polynomial growth; here the growth assumption is replaced by a bi-directional good local sampler for systematic-scan Glauber dynamics. The payoff is quasipolynomial PAC learning of AC0 under hard-core (λ < (1-η)/(Δ-1)) and soft-constraint/Ising models on arbitrary max-degree graphs, regimes that approach the classical sampling thresholds.\n\nWhat is new is the concrete Samp–InvSamp pair built from truncated local resolvers. They introduce determining mark sequences so a fixed initial configuration behaves like a stationary one with high probability, then truncate the automata after polylog steps to get AppSamp/AppInvSamp of controlled degree. Section 4 extends Tal-style Fourier tails to product spaces over finite alphabets via a selector reduction; that piece is clean and reusable. The applications (Lemmas 6.1, 6.3) construct explicit finite-state automata and prove exponential tails by dominating the fresh-call branching process with a negative-drift martingale (Hoeffding/Azuma). The error budget in Lemmas 5.10–5.14 closes with explicit parameter choices.\n\nSoft spots are ordinary for a long combinatorial argument: possible constant-factor slips in the Azuma parameters or alphabet-size bookkeeping, and the local-sampler condition is verified only inside the stated regimes. Outside those regimes the exponential decay can fail and the degree bound collapses, but the paper never claims more. No circular fitting, no invented data, citations look standard.\n\nThis is for people who care about learning under dependent measures or about local-computation sampling. The reduction is self-contained enough that a serious referee can check it. I would send it to peer review and would cite the framework if I work on related questions.","headline":"Solid theory paper that removes CGMV26's poly-growth barrier via truncated Glauber local samplers and gives the first quasipolynomial AC0 learners for hard-core/Ising on general bounded-degree graphs near sampling thresholds.","tokens_in":41369,"tokens_out":466,"would_cite":true,"duration_ms":6098,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W20","60J10","68Q25"],"pacs":[],"model":"grok-4.5","headline":"If a bounded-degree Gibbs measure has a fast local sampler, every constant-depth circuit admits a quasipolynomial-degree L2 approximation under that measure, and is therefore learnable in quasipolynomial time.","keywords":["AC0 learning","Gibbs distributions","Glauber dynamics","local samplers","hard-core model","Ising model","low-degree approximation","graphical models"],"falsifier":"On a fixed expander family, either the hard-core (or soft-constraint) local resolver fails the exponential-decay bound at the stated fugacity or interaction strength, so determining mark sequences become rare, or else an explicit low-depth circuit remains far in L2 from every polylog-degree polynomial under that measure.","tokens_in":41484,"feed_emoji":"🎲","tokens_out":723,"duration_ms":14150,"temperature":0.7,"pith_summary":"The paper shows that constant-depth Boolean circuits (AC0) can be learned from labeled samples drawn from many correlated Gibbs distributions on graphs of bounded degree, without requiring the graph to have polynomial growth. The route is a low-degree approximation theorem: if the distribution admits efficient local samplers built from systematic-scan Glauber dynamics and its reverse, then every AC0 function is close in L2 to a low-degree polynomial under that measure. Truncating those local resolvers after polylogarithmic depth produces an approximate sampler and inverse sampler that transfer ordinary product-space Fourier approximation back to the Gibbs measure. Instantiated for the hard-core model and soft-constraint two-spin systems (including the Ising model), the result yields quasipolynomial PAC learners on arbitrary bounded-degree graphs in regimes approaching classical sampling thresholds. A sympathetic reader cares because previous guarantees for correlated ambient distributions needed strong geometric control that expanders and random graphs lack; local sampleability replaces that geometry.","feed_headline":"Local samplers unlock AC0 learning on general graphs","feed_subtitle":"Truncating Glauber dynamics yields quasipolynomial learners for hard-core and Ising models.","key_machinery":"The Samp–InvSamp pair realized by systematic-scan Glauber dynamics with determining mark sequences, approximated by truncated local automata (AppSamp / AppInvSamp). Truncation keeps circuit complexity and coordinate degree polylogarithmic while preserving the approximate conditional-inversion property needed to move low-degree product approximations onto the Gibbs measure.","core_discovery":"Whenever a Gibbs distribution on a bounded-degree graph admits a bi-directional good local sampler for systematic-scan Glauber dynamics, every function computed by an AC(d,n^c) circuit has an L2 approximation of degree log^{O(d)}(n/ε) under that distribution, which immediately produces a quasipolynomial-time PAC learner. The polynomial-growth assumption used in prior work is thereby removed.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Local samplers enable quasipolynomial AC0 learners on general graphs","Truncated Glauber dynamics yields AC0 learning under local samplers","AC0 learning without polynomial growth via local samplers","Quasipolynomial PAC learners for AC0 under sampleable Gibbs models","Low-degree AC0 approx from truncated Glauber on bounded graphs"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The distribution must have local resolvers that, with fixed constants independent of system size, query only a bounded number of marks or spins per step and terminate with an exponential tail after only a logarithmic number of steps.","fun_headline_variants_meta":{"raw":{"variants":["Local samplers enable quasipolynomial AC0 learners on general graphs","Truncated Glauber dynamics yields AC0 learning under local samplers","AC0 learning without polynomial growth via local samplers","Quasipolynomial PAC learners for AC0 under sampleable Gibbs models","Low-degree AC0 approx from truncated Glauber on bounded graphs"]},"model":"grok-4.5","effort":"low","cost_usd":0.00403,"raw_usage":{"total_tokens":1251,"prompt_tokens":773,"num_sources_used":0,"completion_tokens":72,"cost_in_usd_ticks":40300000,"prompt_tokens_details":{"text_tokens":773,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":406,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":773,"tokens_out":72,"duration_ms":4303,"temperature":1.0,"reasoning_tokens":406,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T09:43:31.794369+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a fixed expander family, either the hard-core (or soft-constraint) local resolver fails the exponential-decay bound at the stated fugacity or interaction strength, so determining mark sequences become rare, or else an explicit low-depth circuit remains far in L2 from every polylog-degree polynomial under that measure.","supporting_citations":[],"review_version":1}