{"id":"4b493514-2265-4d8e-8c89-be80bd66ab11","arxiv_id":"1908.06428","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The approximation ratios of LZ78 and BISECTION are shown to be Θ((n/log n)^(2/3)) and Θ(sqrt(n/log n)), and the RePair lower bound is raised to Ω(log n/log log n).","lead":"This theoretical paper closes two long-standing gaps in the analysis of grammar-based compression, giving tight worst-case approximation ratios for the LZ78 and BISECTION compressors. It also improves the known lower bound for RePair and sharpens a reduction between binary and arbitrary alphabets.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"RePair lower bound proof uses the size of an intermediate grammar as a lower bound, although RePair's grammar size is non-increasing; the claimed Ω(k²/log k) final-size bound is not established.","rationale":"The reader's weakest assumption identifies the same load-bearing problem: Claim 2 of Theorem 3.7 lower-bounds the final RePair grammar by the size of the intermediate grammar after k−1 rounds, despite the fact that RePair's grammar size is non-increasing and later rounds can only shrink it. I checked the size accounting: replacing r occurrences of a length-ℓ string by one nonterminal and adding a rule of length ℓ changes the total size by ℓ − (ℓ−1)r, which is never positive for r ≥ 2, ℓ ≥ 2. Thus the intermediate grammar is larger than or equal to the final grammar, so the proof would need a separate upper bound on the amount of later-round compression. No such bound is provided. This is not a peripheral issue: the RePair lower bound is one of the headline results in the abstract, and the argument as written does not establish it. The LZ78 and BISECTION results appear to be supported by their own detailed constructions, so I would not reject the entire line of work; however, the paper as submitted contains a genuine gap in a central theorem. Since the reader already reached REJECT and my independent check sharpens the same gap, the verdict remains unchanged.","tokens_in":20855,"tokens_out":14683,"duration_ms":154343,"concrete_test":"Implement the RePair variant defined in §3.3 (most frequent maximal string, left-to-right replacement) and run it on the words s_k for k = 4, 6, 8, 10, 12; record the grammar size after k−1 rounds and the final grammar size, and compare the final size to c·k²/log k for a constant c implied by Claim 2. If the final size drops below the claimed Ω(k²/log k) bound, the lower-bound family is falsified; if it stays above, the missing monotonicity step still needs a proof, but the concern would be reduced. The same runs also show whether the total later-round size decrease is o(k²/log k) or Ω(k²/log k).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The decisive gap is in Theorem 3.7, Claim 2. The proof fixes G, the SLP produced after k−1 RePair rounds, shows that its start rule contains Ω(k²) distinct factors of length Θ(log k), and concludes from Lemma 2.1(5) that |RePair(s_k)| = Ω(k²/log k). This inference is invalid. Each RePair round replacing r non-overlapping occurrences of a length-ℓ maximal string by one nonterminal and adding the rule X→γ changes total size by ℓ − (ℓ−1)r, which is ≤ 0 for every legal round (r ≥ 2, ℓ ≥ 2). Hence grammar size is non-increasing, so the size of G after k−1 rounds is an upper bound, not a lower bound, on the final grammar size. The final grammar could in principle be much smaller than G; indeed Claim 1 shows an O(k)-size SLP for s_k exists. No argument is given that all later-round replacements shrink G by only o(k²/log k). This is especially pressing because the a-blocks of s_k have the doubling structure A_{i+1} ≈ A_i A_i, so later rounds may replace large repeated fragments across all k blocks, with a cascade of further reductions. The theorem may be true, but the proof as written does not support it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the worst-case approximation ratio of grammar-based compressors, defined as |C(w)|/g(w), where g(w) is the size of a smallest straight-line program for w. It claims three main results: the approximation ratio of LZ78 is Θ((n/log n)^{2/3}) for every alphabet size k with 2 ≤ k ≤ n; the approximation ratio of BISECTION is Θ(√(n/log n)) for the same range; and the lower bound for RePair is improved from Ω(√log n) to Ω(log n/log log n). The paper also gives a simplification of an Arpe–Reischuk reduction, improving the constant from 24+ε to 6, and a minor result on the exact threshold length 2k²+2k+1 for when every word of length n over a k-letter alphabet has a nontrivial SLP. The proofs for LZ78 and BISECTION are based on explicit word families and use the upper bounds from Charikar et al. as black boxes; the RePair lower bound uses a De Bruijn sequence construction and claims a lower bound on the size of an intermediate grammar's start rule.","tokens_in":21066,"tokens_out":44293,"duration_ms":400629,"significance":"If the results hold, they are significant: they provide the first exact worst-case approximation ratios for two widely used grammar-based compressors, LZ78 and BISECTION, and they improve the known lower bound for RePair in a way that excludes RePair as a candidate for improving Yao's addition-chain method. The LZ78 and BISECTION analyses appear sound, with explicit, parameter-free word families and careful accounting of the factorization and SLP sizes. The binary-alphabet reduction is clean and improves a previously technical construction. The RePair proof is more delicate, but a careful reading shows that the contested final inference can be justified by a short argument that the final grammar, restricted to the nonterminals introduced after the first k−1 rounds, is an SLP for the intermediate start rule with the X_i treated as terminals. The manuscript would benefit from stating this argument explicitly.","major_comments":[],"minor_comments":[{"comment":"The final sentence of Claim 2, saying that the lower bound on a smallest SLP for the start rule of G implies |RePair(s_k)| = Ω(k²/log k), is too terse and can be misread as an invalid comparison with the intermediate grammar size. It is valid for the following reason: the final RePair grammar, after deleting the productions for X_1,...,X_{k−1} and treating those symbols as terminals, is an SLP for the start rule of G, so its size is at least g(start rule of G). Please add this justification explicitly; without it, the proof is easy to misunderstand.","section":"Theorem 3.7, Claim 2 (Section 3.3)"},{"comment":"The example labeled u_{2,4}, v_{2,4}, and s_{2,4} actually instantiates the parameters k=4, m=2, not k=2, m=4. The strings shown are ((a⁴b⁵a)²(a⁴b³)²)⁴a⁴ and (ba⁴b²a⁴)¹⁶, which match the definition for k=4, m=2. Please rename the example to u_{4,2}, v_{4,2}, and s_{4,2}, or change the parameters consistently.","section":"Example 3.5 (Section 3.2)"},{"comment":"Section 4, titled 'Hardness of grammar-based compression for binary alphabets,' is empty in the submitted text. Either restore the intended content or remove the heading, and move the sentence 'The goal of this section is to prove the following result' before Theorem 3.8 to the appropriate location.","section":"Section 4"},{"comment":"Several references contain typos or LaTeX artifacts: reference [16] lists 'SPIRE 2017, volume 9954' but the year 2016 and volume correspond to SPIRE 2016; reference [6] contains 'Springer, 1996. to appear'; and references [13]–[15] contain 'Micha/suppress l' artifacts that should be cleaned up.","section":"References"},{"comment":"The displayed definition of m_k has lost its braces: it should read m_k = 2^{k−⌈log k⌉} − ⌈log k⌉, not the ambiguous '2 k−⌈log2 k⌉ − ⌈log2 k⌉'.","section":"Section 3.1, definition of m_k"},{"comment":"The proof of Proposition 2.2 leaves the verification that the constructed word w_k is not in M_{3,2} ∪ M_{2,3} to 'one can check.' A short argument or a reference to a detailed example would make this minor result easier to verify.","section":"Proposition 2.2"}],"recommendation":"minor_revision","confidential_remarks":"I disagree with the reader's rejection based on Theorem 3.7. The contested inference, while terse, is valid once the final grammar is viewed as an SLP for the intermediate start rule; the missing sentence is easily supplied. The empty Section 4 and the parameter typo in Example 3.5 suggest the submitted source may have formatting errors, and the editor may wish to verify that the manuscript under review is the intended version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuinely useful paper whose central LZ78 and BISECTION results I largely trust, but the RePair lower bound as written does not go through. The referee should not desk-reject it; they should send it back for a serious repair of Theorem 3.7.\n\nWhat is new: exact Θ((n/log n)^{2/3}) for LZ78 and Θ(sqrt(n/log n)) for BISECTION, with binary-alphabet constructions; improved RePair lower bound; reduction factor 6 versus 24+ε. These are real advances over Charikar et al. The word families are intricate, and I don't see circularity or hidden parametric fitting. The LZ78 factorization analysis in Section 3.2 is painstaking and convincing; Claims 1 and 2 line up. Same for BISECTION: the F_k factor set argument is clean, n=Θ(2^{2k}/k), k=Θ(log n) gives the right exponent. If there is a flaw there, I don't see it.\n\nWhere the paper breaks: Theorem 3.7, Claim 2. The proof fixes G, the SLP after k−1 rounds, and argues that the start rule of G has many distinct factors of length Θ(log k), hence |RePair(s_k)| = Ω(k^2/log k). But RePair's total grammar size is non-increasing under replacement: replacing ℓ ≥ 2 by one nonterminal with r ≥ 2 occurrences changes size by ℓ − (ℓ−1)r ≤ 0. So G is an upper bound on the final size, not a lower bound. Later rounds could shrink the grammar substantially. The proof gives no argument that the later rounds only shave o(k^2/log k). This matters because the a-blocks have the doubling structure A_{i+1} ∈ {A_i A_i, A_i A_i a}, so after k−1 rounds there is still a lot of repeated structure across blocks, and RePair could plausibly collapse much of it. The theorem may be true—I suspect it is—but this proof doesn't establish it.\n\nThe rest of the paper holds up. Lemma 3.10 (binary decoding with the ψ-normal form) is intricate; I checked the size bound 2|B| and the confluence claim, and it looks right. The Arpe–Reischuk improvement to factor 6 is a nice, much simpler construction.\n\nWho this is for: anyone working on grammar-based compression, approximation ratios of dictionary compressors, or LZ/RePair lower bounds. The LZ78 and BISECTION halves alone are worth publishing. The RePair half needs an additional idea. I'd send it to a serious referee with a request to focus on Theorem 3.7 and would expect a revised version or a separate corrected proof. Not desk material.","headline":"Tight bounds for LZ78 and BISECTION look right, but the RePair lower bound has a genuine gap: the proof bounds an intermediate grammar, not the final one.","tokens_in":21661,"tokens_out":1668,"would_cite":true,"duration_ms":16150,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper closes the approximation-ratio gaps for LZ78 and BISECTION.","keywords":["string compression","smallest grammar problem","approximation ratio","LZ78","BISECTION","RePair","straight-line program","grammar-based compression"],"falsifier":"Run the paper's exact RePair variant on the constructed binary words $s_k$ for increasing $k$, and compare the grammar size after $k-1$ rounds with the size after RePair reaches its final grammar. If the final grammar is ever $o(k^2/\\log k)$—that is, if later rounds shrink the intermediate grammar enough to break the $\\Omega(k^2/\\log k)$ bound—then the claimed lower bound for RePair is false. The words and algorithm are specified explicitly, so this is a concrete finite test.","tokens_in":20634,"feed_emoji":"📉","tokens_out":14538,"duration_ms":116072,"temperature":0.7,"pith_summary":"The paper settles, up to constant factors, how badly two classic grammar-based compressors can behave in the worst case. For a word, the approximation ratio is the size of the grammar the compressor outputs divided by the size of a smallest straight-line program (SLP) for that word, maximized over all words of length $n$. The paper proves LZ78's worst-case ratio is $\\Theta((n/\\log n)^{2/3})$ for every alphabet size $k$ with $2 \\le k \\le n$, and BISECTION's is $\\Theta(\\sqrt{n/\\log n})$. It also raises the lower bound for RePair from $\\Omega(\\sqrt{\\log n})$ to $\\Omega(\\log n/\\log\\log n)$ using binary words, and improves the alphabet-reduction result from a factor $24+\\varepsilon$ to a factor $6$: a constant-factor approximation for binary strings would give a constant-factor approximation for arbitrary alphabets. These are among the first exact (up to constants) worst-case guarantees for practical grammar compressors, and the lower-bound word families live over binary alphabets.","feed_headline":"LZ78 and BISECTION worst-case ratios are now exactly known","feed_subtitle":"Both match their bounds up to constants; RePair's lower bound rises to log n / log log n.","key_machinery":"The proofs are carried by four explicit constructions and one translation. (1) For BISECTION, the hard word is $s_k = (u_k a^{m_k+1})^{m_k} u_k$, where $u_k$ concatenates the $k$ binary code words of length $\\lceil\\log k\\rceil$ separated by runs $a^{m_k}$; any split into equal power-of-two blocks yields $\\Omega(2^k)$ distinct factors, so BISECTION's SLP is large, while the word has an SLP of size $O(k)$. (2) For LZ78, the hard word is $s_{m,k}=a^{k(k+1)/2}b^{m(2m+1)}u_{m,k}v_{m,k}$ with $u_{m,k}=((a^k b^{2m+1}a)^m(a^k b^{m+1})^2)^k a^k$ and $v_{m,k}=(\\prod_{i=1}^m b^i a^k)^{k^2}$; the unique LZ78 factorization is shown to produce $\\Theta(k^2 m)$ distinct phrases. (3) For RePair, the hard word is $s_k=\\prod_{i=1}^{k-1}(a\\,w_k[1:k+i]\\,b)\\,a\\,w_k$, where $w_k$ comes from a binary sequence of order $\\lceil\\log k\\rceil$ in which each length-$\\lceil\\log k\\rceil$ word occurs once, mapped by $0\\mapsto 01$, $1\\mapsto 10$; after $k-1$ rounds the start rule already contains $\\Omega(k^2/\\log k)$ distinct length-$\\Theta(\\log k)$ patterns, forcing a large grammar. (4) The alphabet reduction uses $\\varphi(c_i)=a^i b$, with lemmas showing any SLP over the large alphabet becomes an SLP for the binary image with size at most $3|A|$, and any SLP for a binary image can be converted back with size at most $2|B|$, giving the factor $6c$.","core_discovery":"The central discovery is that the gaps left by earlier analysis of the smallest grammar problem can be closed with explicit word families. For BISECTION, a family of binary words is constructed whose optimal grammar has size $O(k)$ while BISECTION must generate $\\Omega(2^k)$ distinct nonterminals when splitting into power-of-two blocks; this yields ratio $\\Omega(2^k/k)$, and since the word length is $n = \\Theta(2^{2k}/k)$, ratio $\\Omega(\\sqrt{n/\\log n})$. For LZ78, the word family $s_{m,k}$ forces $\\Theta(k^2 m)$ distinct LZ78 factors while the optimal grammar has size $O(\\log k + m)$; taking $m = \\lceil\\log k\\rceil$ gives ratio $\\Omega(k^2)$, and with $n = \\Theta(k^3 \\log k)$ this is $\\Theta((n/\\log n)^{2/3})$. For RePair, binary words built from a sequence in which every length-$\\lceil\\log k\\rceil$ block occurs exactly once force any grammar for the intermediate start rule to have size $\\Omega(k^2/\\log k)$ while the whole word has an SLP of size $O(k)$, yielding $\\Omega(\\log n/\\log\\log n)$. Finally, the homomorphism $\\varphi(c_i)=a^i b$ translates SLPs between arbitrary and binary alphabets with constant-factor size changes in both directions, improving the alphabet-reduction constant from $24+\\varepsilon$ to $6$.","pith_inferences":["The paper establishes asymptotic $\\Theta$ bounds but does not extract the hidden constants; computing them for the constructed families would show at which finite lengths the worst cases become visible, a natural next step the paper leaves open.","The BISECTION lower bound relies on the algorithm's fixed power-of-two splitting rule; a natural (untested) extension is that a variant splitting at the midpoint or at another balanced point might evade the $\\Omega(\\sqrt{n/\\log n})$ ratio.","The alphabet-reduction constant $6$ is one factor away from $8569/8568$, the threshold that would transfer the known inapproximability of the smallest grammar problem to binary strings; optimizing the encoding further is a promising direction.","The technique of fully characterizing the LZ78 factorization of a crafted word may also yield exact ratios for variants such as LZW or for online dictionary compressors, though the paper does not analyze them."],"forward_implications":["For every alphabet size $k$ with $2 \\le k \\le n$, no algorithm can improve LZ78's worst-case output beyond a constant factor of $(n/\\log n)^{2/3}$ times the optimal grammar: the ratio is asymptotically tight.","BISECTION's worst-case output is asymptotically tight at $\\Theta(\\sqrt{n/\\log n})$ times optimal, matching the earlier upper bound.","RePair's approximation ratio is at least $\\Omega(\\log n/\\log\\log n)$, so RePair cannot serve as the polynomial-time compressor with ratio $o(\\log n/\\log\\log n)$ that would resolve the long-standing addition-chain problem.","A constant-factor approximation for binary strings would imply a factor-$6$ constant-factor approximation for arbitrary alphabets, improving the previous factor $24+\\varepsilon$.","All lower bounds hold over binary alphabets, so the hardness is not an artifact of unbounded alphabets."],"supporting_citations":[{"why":"Defines the approximation-ratio framework and supplies the upper bounds that the new lower bounds match, plus the previous RePair lower bound to be improved.","marker":"[7]"},{"why":"Defines LZ78 and the unique factorization whose phrase count is the object of the LZ78 lower-bound analysis.","marker":"[39]"},{"why":"Defines the BISECTION (multilevel pattern matching) compressor whose worst-case output size is analyzed.","marker":"[22]"},{"why":"Defines RePair, the global grammar compressor whose lower bound is improved to $\\Omega(\\log n/\\log\\log n)$.","marker":"[26]"},{"why":"Gives the previous $24c+\\varepsilon$ alphabet-reduction result that the paper improves to $6c$.","marker":"[2]"},{"why":"Supplies the binary sequences with every length-$\\lceil\\log k\\rceil$ block occurring exactly once, used to build the RePair hard words.","marker":"[9]"},{"why":"Proves the $\\Theta(n/\\log_\\sigma n)$ bound on smallest SLP size that the compact-grammar constructions rely on.","marker":"[3]"},{"why":"Identifies the addition-chain problem whose connection to small-ratio grammar compressors makes the RePair lower bound significant.","marker":"[38]"}],"fun_headline_variants":["LZ78 and BISECTION worst-case ratios exactly known","Exact ratios for LZ78 and BISECTION in smallest grammar","RePair lower bound raised to log n / log log n","Gaps closed for LZ78, BISECTION, and RePair in grammar"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The RePair lower-bound proof assumes that the grammar after the first $k-1$ replacement rounds is a lower bound on the size of RePair's final grammar; if later rounds can compress that intermediate grammar below $\\Omega(k^2/\\log k)$, the claimed lower bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["LZ78 and BISECTION worst-case ratios exactly known","Exact ratios for LZ78 and BISECTION in smallest grammar","RePair lower bound raised to log n / log log n","Gaps closed for LZ78, BISECTION, and RePair in grammar"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001214,"raw_usage":{"total_tokens":5027,"prompt_tokens":1004,"completion_tokens":4023,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":3945}},"tokens_in":620,"tokens_out":4023,"duration_ms":29642,"temperature":1.0,"reasoning_tokens":3945,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:48:32.743960+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's exact RePair variant on the constructed binary words $s_k$ for increasing $k$, and compare the grammar size after $k-1$ rounds with the size after RePair reaches its final grammar. If the final grammar is ever $o(k^2/\\log k)$—that is, if later rounds shrink the intermediate grammar enough to break the $\\Omega(k^2/\\log k)$ bound—then the claimed lower bound for RePair is false. The words and algorithm are specified explicitly, so this is a concrete finite test.","supporting_citations":[{"cited_title":"Charikar, E","cited_arxiv_id":null,"evidence_quote":"Defines the approximation-ratio framework and supplies the upper bounds that the new lower bounds match, plus the previous RePair lower bound to be improved."},{"cited_title":"Compression of individua l sequences via variable-rate cod- ing","cited_arxiv_id":null,"evidence_quote":"Defines LZ78 and the unique factorization whose phrase count is the object of the LZ78 lower-bound analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the BISECTION (multilevel pattern matching) compressor whose worst-case output size is analyzed."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines RePair, the global grammar compressor whose lower bound is improved to $\\Omega(\\log n/\\log\\log n)$."},{"cited_title":"On the complexity of opti mal grammar-based compres- sion","cited_arxiv_id":null,"evidence_quote":"Gives the previous $24c+\\varepsilon$ alphabet-reduction result that the paper improves to $6c$."},{"cited_title":"A combinatorial problem","cited_arxiv_id":null,"evidence_quote":"Supplies the binary sequences with every length-$\\lceil\\log k\\rceil$ block occurring exactly once, used to build the RePair hard words."},{"cited_title":"On the length of word chain s","cited_arxiv_id":null,"evidence_quote":"Proves the $\\Theta(n/\\log_\\sigma n)$ bound on smallest SLP size that the compact-grammar constructions rely on."},{"cited_title":"On the evaluation of powers","cited_arxiv_id":null,"evidence_quote":"Identifies the addition-chain problem whose connection to small-ratio grammar compressors makes the RePair lower bound significant."}],"review_version":1}