{"id":"71e27f94-f91a-4d83-b004-92e8b2850a79","arxiv_id":"2607.08566","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"GD string matching admits a classical Õ(N√m) algorithm, and combinatorial GD/ED indices cannot improve the known m-dependence under the k-clique conjecture.","lead":"The paper gives a classical Õ(N√m)-time algorithm for pattern matching on generalized degenerate strings, closing the last open boundary case between near-linear and SETH-hard variable-string matching. It also supplies matching combinatorial indexing lower bounds for GD and ED strings under standard fine-grained hypotheses.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates Theorem 3 as the strongest claim and correctly notes that the combinatorial lower bounds rest on the k-clique conjecture and the Bringmann-style gadgets. Those lower-bound assumptions are standard and do not undermine the algorithmic upper bound that places GD matching on the subquadratic side of the Ascone et al. dichotomy. Because the upper-bound proof is elementary and free of non-standard hypotheses, no load-bearing concern arises that would justify changing the ACCEPT verdict. The suggested algebraic re-derivation is a low-cost sanity check that would still be worth performing, but it is not expected to fail.","tokens_in":15479,"tokens_out":413,"duration_ms":4409,"concrete_test":"Independently re-derive the total running time of Lemma 2 after the choice τ_k = √(L m log m / B_k), then apply Cauchy–Schwarz exactly as written in the proof of Theorem 3 (∑√B_k ≤ O(√(N log L))); confirm that the resulting expression is O(N + √(N L m log L log m)). If the algebra holds, the central claim is secure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 3) is the Õ(N√m) classical algorithm for GDSM. Its derivation is self-contained: heavy/light classification of width-k strings via the suffix tree of P, FFT convolution for heavy strings, direct occurrence counting for light strings, and a Cauchy–Schwarz aggregation over widths that yields the √(N L m log L log m) bound. All steps use only standard tools (suffix trees, FFT, KMP) and the equal-width restriction of GD strings; no hidden assumption appears to be required for correctness. The indexing lower bounds rest on standard fine-grained hypotheses and gadgets adapted from Bringmann et al., but they are secondary to the strongest claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies pattern matching and indexing for generalized degenerate (GD) strings, the remaining boundary case in the Ascone et al. taxonomy of variable-string matching. For offline matching it gives a classical algorithm running in O(N + √(N L m log L log m)) = Õ(N √m) time (Theorem 3), obtained by a heavy/light decomposition of width-k strings, FFT convolution for heavy strings, direct occurrence counting for light strings, and Cauchy–Schwarz aggregation over widths (Lemma 2). For indexing it adapts Gibney’s ED index to obtain O(nm) query time after linear preprocessing of a GD text (Theorem 4). On the lower-bound side it shows, under OVH/SETH, that no polynomial-preprocessing GD index can achieve O(n^{1-ε} m^{O(1)} + m) query time; under the k-clique conjecture it rules out combinatorial GD indices with O(n^{O(1)} m^{1-ε} + m) queries and combinatorial ED indices with O(n^{O(1)} m^{2-ε}) queries; and under OMv it shows that active-prefix queries cannot be answered in O(m^{2-ε}) time after polynomial preprocessing of the string set and pattern.","tokens_in":15677,"tokens_out":1177,"duration_ms":10218,"significance":"The offline algorithm closes the main open case left by Ascone et al. (WABI 2024) and places GD matching firmly on the subquadratic side of the fine-grained dichotomy for variable strings, complementing the earlier quantum Õ(√(m n N)) result of Equi et al. The indexing upper and lower bounds give a coherent picture: the O(nm) GD index is essentially optimal for combinatorial algorithms under k-clique, while the O(nm^{2}) ED index of Gibney is likewise tight for combinatorial algorithms and for any approach whose bottleneck is active-prefix queries. The reductions are from standard hypotheses (OVH, k-clique, OMv) and the string gadgets are explicit adaptations of Bringmann et al., so the conditional claims rest on well-studied foundations. The work therefore both settles a concrete open problem and sharpens the landscape of what further improvements would require.","major_comments":[{"comment":"The combinatorial lower bounds (Theorems 11 and 14) rest on the correctness of the string gadgets adapted from Bringmann et al. (Lemmas 9/12 and Corollaries 10/13). While the constructions are written carefully, the manuscript never supplies an independent verification that the equal-width (GD) or variable-length (ED) concatenation rules preserve clique structure exactly as claimed. A short self-contained correctness argument, or an explicit reference to the precise lemma in Bringmann et al. that is being reused, would make the load-bearing reductions fully checkable without external consultation.","section":null},{"comment":"Section 4.1 correctly identifies a potential flaw in Gibney’s claimed β < 1 lower bound (the additive +m term already solves OV). The paper leaves open whether a corrected SETH-based lower bound forbidding O(n^{O(1)} m^{1-ε} + m) ED queries exists. Because the subsequent k-clique and OMv results are presented as partial substitutes, a clearer statement of what remains open under SETH alone would help the reader assess the strength of the overall indexing picture.","section":null}],"minor_comments":[{"comment":"In the proof of Lemma 2 the heavy/light threshold is set to τ_k = √(L m log m / B_k). The subsequent Cauchy–Schwarz step in Theorem 3 uses √(1/k) N_k; a one-line remark that the log factors can be absorbed into the Õ notation would improve readability.","section":null},{"comment":"Figure 2 and Figure 3 are helpful but the caption of Figure 2 is dense. Expanding the definition of the four bit-vectors V_easy, V_suf, V_pref, V_anchor in the caption (or moving a short paragraph into the main text) would make the case analysis easier to follow.","section":null},{"comment":"The notation N_ε for the number of empty strings appears only in the size definition of ED strings and is never used again; it can be dropped or briefly justified.","section":null},{"comment":"A few typographical issues: “Ageneralized” (missing space) in the abstract, “Ts(p)” versus T_s(p) inconsistency in Figure 2, and occasional missing spaces after periods in the arXiv source.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a clean, well-written contribution that settles a concrete open problem identified by Ascone et al. The only load-bearing points that need a little more care are the self-contained verification of the clique gadgets and a sharper statement of the remaining SETH gap for ED indexing; both are easily fixable. I see no reason to delay acceptance beyond a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The main result is the first classical subquadratic algorithm for generalized-degenerate pattern matching: Õ(N√m) via heavy/light classification of equal-width strings, FFT convolution on the heavy ones, direct occurrence counting on the light ones, and a Cauchy–Schwarz sum over widths. That places GD firmly on the subquadratic side of the Ascone et al. dichotomy and answers the open classical question they left. The four-case decomposition (easy/suffix/prefix/anchor) is standard, but the anchor handling is new and carefully written.\n\nThe indexing side is also useful. Adapting Gibney’s ED index to GD gives O(nm) queries after linear preprocessing; the equal-width restriction makes the Aho–Corasick and suffix-tree work clean. The combinatorial lower bounds under k-clique (m^{1-ε} for GD, m^{2-ε} for ED) reuse Bringmann-style gadgets and look correct; they match the known upper bounds in the combinatorial regime. The OMv lower bound for indexed active-prefix queries is a clean re-reading of Bernardini et al. and explains why beating O(n^{O(1)}m^{2}) for ED indexing will need both algebraic techniques and a different bottleneck.\n\nSoft spots are minor. No code or experiments, but this is pure theory and the proofs are self-contained. The paper itself flags a possible gap in Gibney’s earlier SETH claim for the m^{1-ε} ED barrier and does not overclaim there. The gadgets assume the usual clique-conjecture setting; if those fail the barriers fall, but that is the standard risk for this style of result.\n\nThis is for people working on fine-grained string algorithms or pangenomics indexes. The math checks out, the citations are honest, and the central claim is solid. I would send it to peer review without hesitation and would cite the upper bound and the active-prefix barrier myself.","headline":"Clean classical Õ(N√m) algorithm that settles the last open GD case in the Ascone taxonomy, plus solid combinatorial indexing barriers.","tokens_in":16326,"tokens_out":495,"would_cite":true,"duration_ms":5632,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W32","68Q25"],"pacs":[],"model":"grok-4.5","headline":"Generalized-degenerate string matching admits a classical Õ(N√m)-time algorithm, placing it on the subquadratic side of the variable-string complexity boundary.","keywords":["generalized degenerate strings","elastic-degenerate strings","pattern matching","fine-grained complexity","text indexing","k-clique conjecture","OMv conjecture"],"falsifier":"A combinatorial algorithm answering GD queries in O(n^{O(1)} m^{1-ε}+m) time after polynomial preprocessing, or an explicit counter-example showing that the adapted Bringmann-style gadgets fail to preserve k-clique structure when all strings inside a segment must have identical length.","tokens_in":16356,"feed_emoji":"🔍","tokens_out":759,"duration_ms":17156,"temperature":0.7,"pith_summary":"Variable strings range from simple degenerate strings to fully elastic-degenerate texts; Ascone et al. left generalized-degenerate (GD) strings—the intermediate case in which every segment contains equal-length strings whose common length may vary—as the last open boundary between near-linear algorithms and SETH-hard quadratic lower bounds. This paper supplies a classical algorithm that decides whether a solid pattern of length m occurs in a GD text of total size N in Õ(N√m) time, settling the question on the subquadratic side. The same techniques yield a linear-preprocessing index answering GD queries in O(nm) time. Matching combinatorial lower bounds under the k-clique conjecture show that the linear dependence on m for GD and the quadratic dependence for elastic-degenerate strings are essentially optimal for combinatorial methods, while an OMv reduction proves that the active-prefix primitive used by existing elastic-degenerate algorithms cannot be improved below quadratic time.","feed_headline":"GD string matching falls to nearly O(N √m) time","feed_subtitle":"The last open boundary case in variable-string matching moves to the subquadratic side.","key_machinery":"Heavy-light decomposition of the strings of each fixed width according to their frequency in the pattern: heavy strings are handled by FFT convolution of binary indicator arrays; light strings are handled by direct reporting of their few occurrences into the candidate array.","core_discovery":"A solid pattern of length m can be matched against a generalized-degenerate text of total size N in Õ(N√m) time by computing, for every candidate starting column, the exact number of fully covered segments that the pattern matches and comparing that count with the number of segments the alignment spans.","pith_inferences":["The heavy-light-plus-convolution technique may adapt directly to founder graphs, the still-open graph analogue of GD strings.","Matching the quantum Õ(√(Nmn)) bound classically would likely need algebraic rather than purely combinatorial methods.","Beating the ED quadratic barrier without abandoning active-prefix queries would require genuinely non-combinatorial techniques."],"forward_implications":["GD pattern matching now belongs with the subquadratic family of variable-string problems rather than the SETH-hard family.","GD texts admit an index with linear preprocessing and O(nm) query time.","No combinatorial GD index can improve the pattern-length dependence below linear under the k-clique conjecture.","No combinatorial ED index can improve the pattern-length dependence below quadratic under the same conjecture.","Active-prefix queries require essentially quadratic time after polynomial preprocessing under OMv, blocking straightforward improvements to existing ED indexes."],"fun_headline_variants":["GD matching lands at Õ(N√m), closing the last variable-string boundary","Solid patterns match GD texts in Õ(N√m) time","GD string matching algorithm reaches subquadratic Õ(N√m)","Indexing lower bounds pin GD queries near linear while ED stays quadratic","Active-prefix bottleneck blocks faster combinatorial ED indexes under OMv"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The combinatorial lower bounds stand only if the k-clique conjecture is true and if the string gadgets correctly encode clique extensions under the equal-width constraints of GD strings.","fun_headline_variants_meta":{"raw":{"variants":["GD matching lands at Õ(N√m), closing the last variable-string boundary","Solid patterns match GD texts in Õ(N√m) time","GD string matching algorithm reaches subquadratic Õ(N√m)","Indexing lower bounds pin GD queries near linear while ED stays quadratic","Active-prefix bottleneck blocks faster combinatorial ED indexes under OMv"]},"model":"grok-4.5","effort":"low","cost_usd":0.005902,"raw_usage":{"total_tokens":1687,"prompt_tokens":959,"num_sources_used":0,"completion_tokens":97,"cost_in_usd_ticks":59020000,"prompt_tokens_details":{"text_tokens":959,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":631,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":959,"tokens_out":97,"duration_ms":6125,"temperature":1.0,"reasoning_tokens":631,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T05:13:24.789540+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"A combinatorial algorithm answering GD queries in O(n^{O(1)} m^{1-ε}+m) time after polynomial preprocessing, or an explicit counter-example showing that the adapted Bringmann-style gadgets fail to preserve k-clique structure when all strings inside a segment must have identical length.","supporting_citations":[],"review_version":1}