{"id":"bb4bf035-f682-4384-8ef6-6f7b09170adc","arxiv_id":"2406.18224","paper_version":3,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":9.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"First FPRAS for #CFG (words of exact length n) and #DNNF (model counting).","lead":"The paper claims the first fully polynomial-time randomized approximation schemes for exactly counting words of length n generated by any context-free grammar and for counting satisfying assignments to any DNNF circuit. These results close a long-open gap between quasi-polynomial algorithms and restricted special cases in approximate counting.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"FPRAS runtime bound may hide non-polynomial dependence on grammar/circuit size via non-standard encoding","rationale":"The reader's diagnosis is exactly the load-bearing point: without an explicit polynomial bound on input size in the runtime, the FPRAS claim cannot be verified from the abstract alone. Full-text inspection of the theorem statement is the direct test; no other internal inconsistency is visible from the given material.","tokens_in":1662,"tokens_out":328,"duration_ms":16008,"concrete_test":"Locate the main theorem (likely Theorem 1 or 2) stating the FPRAS runtime; extract the precise polynomial and verify that every occurrence of grammar size, number of productions, DNNF size, or number of gates appears inside the poly; if any parameter is omitted or treated as constant, recompute the claimed time on a family of grammars whose encoding size is exponential in that parameter.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is an FPRAS whose runtime must be polynomial in the total input size (grammar or DNNF description) plus n and 1/ε. The abstract states the problems as 'Given a CFG G' and 'Given a circuit φ in DNNF' but supplies no explicit encoding convention or size measure. If productions or gates can be encoded so that |G| or |φ| grows exponentially in the parameters appearing in the claimed poly-time bound, the scheme fails to be fully polynomial. This matches the reader's weakest_assumption and is the least secure precondition for the claim to hold.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript claims to provide the first fully polynomial-time randomized approximation scheme (FPRAS) for two problems: (1) given a context-free grammar G over alphabet Σ, approximate the number of words of length exactly n generated by G; (2) given a circuit φ in DNNF over Boolean variables X, approximate the number of satisfying assignments. It positions this as resolving a longstanding open problem, improving on quasi-polynomial runtimes (SODA 1995) and FPRAS results restricted to NFAs (JACM 2021) or tree automata (STOC 2021).","tokens_in":1764,"tokens_out":537,"duration_ms":10922,"significance":"If the algorithmic constructions and error analyses hold with the stated guarantees, the result would be a notable advance in approximate counting, supplying the first FPRAS for #CFG and #DNNF and closing the gap from quasi-polynomial or restricted cases. The manuscript would earn credit for delivering an explicit algorithmic scheme rather than a non-constructive existence argument.","major_comments":[{"comment":"The main theorem statements (presumably in §3 and §5) and runtime analysis must explicitly define the input-size measure for G and φ (e.g., number of productions/gates, total bit length under a standard encoding). Without this, it is impossible to verify that the claimed poly(n, 1/ε, |G|) or poly(n, 1/ε, |φ|) bound is fully polynomial rather than hiding super-polynomial dependence on a non-standard encoding of the grammar or circuit.","section":"Main theorems / runtime analysis"},{"comment":"The reduction or dynamic-programming construction used to obtain the FPRAS (likely in the technical sections deriving the sampling or estimation procedure) must be shown to run in time polynomial in the explicit size of the input grammar/circuit; any auxiliary data structures whose size is exponential in the number of non-terminals or variables would invalidate the FPRAS claim.","section":"Algorithm description / proof of runtime"}],"minor_comments":[{"comment":"Clarify the precise approximation guarantee (additive vs. multiplicative, relative error) and the failure probability in the theorem statements.","section":"Theorem statements"},{"comment":"Add a short comparison table or paragraph contrasting the new runtime with the SODA 1995 quasi-polynomial bound and the restricted automata results.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their careful reading and for highlighting the need for explicit input-size definitions and runtime bounds. We address the two major comments below and will incorporate clarifications into the revised manuscript.","responses":[{"response":"We agree that explicit definitions are required for verifiability. The manuscript already uses |G| to denote the total bit length of a standard encoding of the grammar (summed lengths of all productions, including nonterminal and terminal symbols) and |φ| to denote the number of gates in the DNNF. The claimed runtimes are polynomial in these quantities, n, and 1/ε. In the revision we will add a short paragraph in the Preliminaries explicitly stating these measures and confirming that all algorithms and analyses are polynomial in them.","revision_made":"yes","referee_comment":"[Main theorems / runtime analysis] The main theorem statements (presumably in §3 and §5) and runtime analysis must explicitly define the input-size measure for G and φ (e.g., number of productions/gates, total bit length under a standard encoding). Without this, it is impossible to verify that the claimed poly(n, 1/ε, |G|) or poly(n, 1/ε, |φ|) bound is fully polynomial rather than hiding super-polynomial dependence on a non-standard encoding of the grammar or circuit."},{"response":"The dynamic-programming tables and sampling procedures are sized polynomially in |G| (or |φ|) and n; the number of nonterminals is at most |G|, and the DNNF gate count directly bounds the state space. No auxiliary structures exponential in the number of nonterminals or variables appear in the constructions. We will expand the runtime lemmas in Sections 4 and 6 to include an explicit accounting of every data structure in terms of |G| and |φ|.","revision_made":"yes","referee_comment":"[Algorithm description / proof of runtime] The reduction or dynamic-programming construction used to obtain the FPRAS (likely in the technical sections deriving the sampling or estimation procedure) must be shown to run in time polynomial in the explicit size of the input grammar/circuit; any auxiliary data structures whose size is exponential in the number of non-terminals or variables would invalidate the FPRAS claim."}],"tokens_in":1352,"tokens_out":504,"duration_ms":15783,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The central result is an FPRAS for two problems that had resisted fully polynomial randomized approximation: counting words of length exactly n generated by an arbitrary CFG, and counting satisfying assignments to an arbitrary DNNF. The abstract positions this as the first such scheme without the syntactic restrictions used in the 2021 automata papers, and it improves on the SODA 1995 quasi-polynomial bound. That is the main thing to take away. The work is technically grounded in the sense that it directly targets the open cases rather than carving out easier fragments. The statement of the problems is clean and the contrast with prior results is explicit. If the algorithm and its analysis hold, the result organizes a slice of the approximation landscape for formal-language and knowledge-compilation counting. The soft spot worth checking is the precise dependence on input size. An FPRAS must be polynomial in the total size of the grammar or circuit description plus n and 1/ε. The abstract does not spell out the encoding convention, so the full paper needs to confirm that the running-time bound uses the standard measure (number of productions, nonterminals, and symbols for the grammar; number of gates and variables for the DNNF) and does not hide an exponential factor through a non-standard representation. That is a standard point to verify rather than a fatal gap. No circular definitions or invented quantities appear in the claim itself. The paper is for people working on counting problems in automata, circuits, and knowledge compilation. A reader who follows approximation algorithms for #P-complete tasks or who needs practical counting routines for these representations will get direct value. It deserves a serious referee because the claim is sharp, the prior gap is real, and the result would be cited if the proof checks out. Recommendation: send to peer review.","headline":"The paper gives the first FPRAS for exact-n word counting under CFGs and model counting under DNNFs, moving past the 1995 quasi-polynomial barrier.","tokens_in":2251,"tokens_out":437,"would_cite":false,"duration_ms":15872,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"FPRAS via derivation-tree overlap sampling for #CFG/#DNNF is orthogonal to RS","alignment":"orthogonal","rationale":"The paper reduces #CFG/#DNNF to support-counting in homogeneous multilinear (+,×) programs, then deploys bottom-up sampling (reduce+union) whose variance is controlled by the size of lcsn overlaps of derivation trees (Lemmas 7-10, 14-15). This is standard algorithmic analysis with no ratio-symmetric cost J, no golden-ratio identities, no 8-tick periodicity, and no parameter-free derivation of constants. RS modules (AbsoluteFloorClosure.lean, ArithmeticFromLogic.lean, Cost/FunctionalEquation.lean, AlexanderDuality.lean) contain none of these structures; the domains are disjoint.","tokens_in":66218,"confidence":"high","tokens_out":179,"duration_ms":6175,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Context-free grammars and DNNF circuits admit fully polynomial-time randomized approximation schemes for counting.","keywords":["context-free grammar","DNNF","counting problems","approximation scheme","randomized algorithm","polynomial time","model counting","word counting"],"falsifier":"A concrete CFG or DNNF instance on which the approximation procedure fails to stay within a (1+epsilon) multiplicative error of the true count with the stated success probability while running in the claimed polynomial time bound.","tokens_in":2545,"feed_emoji":"","tokens_out":457,"duration_ms":23753,"temperature":0.7,"pith_summary":"The paper gives the first fully polynomial-time randomized approximation scheme for counting the number of words of exact length n generated by a context-free grammar. It gives the same kind of scheme for counting the satisfying assignments of a DNNF circuit. These counting tasks previously had only quasi-polynomial time solutions or worked only for restricted cases such as automata. A reader would care because the new schemes make approximation possible in time polynomial in the input size and the desired accuracy.","feed_headline":"Polynomial approximations reach CFG word counts and DNNF models","feed_subtitle":"The schemes work for exact-length strings and satisfying assignments with arbitrary accuracy and high probability.","key_machinery":"A fully polynomial-time randomized approximation scheme that estimates the count to within a (1+epsilon) factor with high probability in time polynomial in the input size, 1/epsilon, and log(1/delta).","core_discovery":"We provide the first fully polynomial-time randomized approximation scheme for counting the number of words of length exactly n generated by a CFG and the number of assignments satisfying a DNNF circuit. Finding polynomial time algorithms for the aforementioned problems has been a longstanding open problem. Prior work could either only obtain a quasi-polynomial runtime or a polynomial-time randomized approximation scheme for restricted fragments such as non-deterministic finite automata or non-deterministic tree automata.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["FPRAS for CFG word counts and DNNF models","CFG counting and DNNF models get FPRAS","Poly randomized approx for CFG and DNNF","FPRAS for CFG n-words and DNNF models"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The grammar or DNNF is presented in a standard encoding whose size is polynomial in the parameters that appear in the running-time bound of the claimed approximation scheme.","fun_headline_variants_meta":{"raw":{"variants":["FPRAS for CFG word counts and DNNF models","CFG counting and DNNF models get FPRAS","Poly randomized approx for CFG and DNNF","FPRAS for CFG n-words and DNNF models"]},"model":"grok-4.3","cost_usd":0.008299,"raw_usage":{"total_tokens":3725,"prompt_tokens":596,"num_sources_used":0,"completion_tokens":54,"cost_in_usd_ticks":82987000,"prompt_tokens_details":{"text_tokens":596,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3075,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":596,"tokens_out":54,"duration_ms":15083,"temperature":1.0,"reasoning_tokens":3075,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-23T23:54:30.349838+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete CFG or DNNF instance on which the approximation procedure fails to stay within a (1+epsilon) multiplicative error of the true count with the stated success probability while running in the claimed polynomial time bound.","supporting_citations":[],"review_version":1}