The Random Subsequence Model and Uniform Codes for the Deletion Channel
Ryan Jeong, Francisco Pernice
Abstract
We introduce the Random Subsequence Model, a spin glass model on pairs of random strings whose partition function counts subsequence embeddings of into . We study two variants: the null model, where and are independent and uniform, and the planted model, where is uniform and is a uniformly-random length- subsequence of . We connect the Random Subsequence Model to longstanding problems in various fields, including the best rate achievable by uniformly-random codes in the deletion channel, the longest common subsequence problem between two random strings, and models of directed polymers in statistical physics. In the regime where at a fixed ratio , we exhibit strict asymptotic separations between the null annealed free energy and the quenched free energies of the null and planted models at all values of the density parameter . This suggests that these models are in a spin glass phase at zero temperature throughout the entire dense regime. As a consequence, we show that uniformly-random codes achieve a positive rate in the deletion channel for all deletion probabilities settling multiple conjectures of the second author, Isik and Weissman (2024) and proving the first such positive rate result for the regime . We also give an exact analytic formula for the annealed free energy of the planted model for all values of the density parameter. This implies a corresponding analytic upper bound on the best rate achievable by uniformly-random codes in the deletion channel, complementing the lower bound from our first result. Our upper and lower bounds for the capacity of the deletion channel under uniform codes are far closer to each other than the best known upper and lower bounds for the capacity of the deletion channel.
AI Impact Assessments
(3 models)Scientific Impact Assessment: The Random Subsequence Model and Uniform Codes for the Deletion Channel
1. Core Contribution
This paper introduces the Random Subsequence Model, a spin glass model whose partition function counts subsequence embeddings of one random binary string into another. The paper studies null (independent strings) and planted (one string is a subsequence of the other) variants and establishes three main results:
1. Theorem 1.1: Strict separations between null annealed free energy and quenched free energies of both null and planted models for all density parameters α ∈ (0,1), suggesting a spin glass phase throughout the dense regime.
2. Corollary 1.2: Uniformly-random codes achieve positive rate in the binary deletion channel for *all* deletion probabilities p ∈ [0,1), settling conjectures from [PIW24] and providing the first positive-rate result for the regime p ≥ 1/2.
3. Theorem 1.3: An exact closed-form formula for the annealed free energy of the planted model, yielding analytic upper bounds on the uniform capacity.
The central problem addressed—understanding the capacity of the deletion channel—has been open for decades and is widely regarded as one of the most fundamental unsolved problems in information theory. The paper makes significant progress on the relaxed problem of uniform capacity.
2. Methodological Rigor
The paper demonstrates exceptional methodological sophistication, drawing from statistical physics, probabilistic combinatorics, information theory, and analytic combinatorics.
For Theorem 1.1, the proof strategy is particularly innovative. The authors construct a hypothesis testing framework via "good sets" G(x), using block-level alignment statistics to distinguish planted from null models. The key technical challenge—controlling induced total alignment uniformly over exponentially many near-equipartitions—is handled through the standardization algorithm (Definition 3.10), which approximates induced near-equipartitions by a much smaller class of standardized ones. The proof that biased stretches are rare (Proposition 3.12) and the uniform approximation bound (equation 3.22) are carefully executed.
The weak limit proofs (Section 2) use superadditive ergodic theory for the planted model and a more delicate argument exploiting self-replicating structure for the null model, where genuine superadditivity can fail. The skip vector encoding for the lower bound on f_null is elegant.
For Theorem 1.3, the proof proceeds through a clean variational analysis. Lemma 4.1's "gap product formula" reduces the combinatorial problem to compositions. The passage to a variational problem over empirical measures (Theorem 4.8) is rigorous, with careful treatment of Stirling approximations and support bounds. The closed-form evaluation of Z(x,y) via residue methods (Lemma 4.10) and the resolution of the resulting algebraic system (Proposition 4.12) are technically complete.
The Nishimori identity connecting null and planted models (equation 2.17) provides a clean structural link between the two variants.
3. Potential Impact
Information Theory: The resolution of [PIW24, Conjecture 3] is significant. The result that uniform codes work for all p < 1 changes the landscape of what is known about deletion channel coding. The upper and lower bounds on uniform capacity (Figure 1) are strikingly close—far tighter than existing bounds on full capacity—suggesting uniform capacity may be tractable.
Probability and Combinatorics: The connection to the longest common subsequence (LCS) problem (Section 1.1.2) positions the Random Subsequence Model as a natural "slice" of the LCS partition function framework. Progress here could inform the 50-year-old Chvátal-Sankoff problem.
Statistical Physics: The model provides a new instance of a rank-one directed polymer in random environment, distinct from the well-studied i.i.d. case. The suggestion that the Strict-Weak Polymer Model (with its exact solution) approximates the Random Subsequence Model (Figure 2) opens concrete research directions.
Coding Theory: The explicit lower bound (Theorem 3.13) with polynomial decay Ω((1-p)^k) as p→1, combined with the known upper bound O((1-p)^{4/3} log(1/(1-p))), pins down the qualitative behavior of uniform capacity near p=1.
4. Timeliness & Relevance
The deletion channel capacity problem is a longstanding bottleneck in information theory. Recent renewed interest, including [PIW24]'s conjectures and computational approaches, makes this work highly timely. The spin glass perspective connects to the vibrant research area at the intersection of statistical physics and combinatorial optimization.
5. Strengths & Limitations
Strengths:
Limitations:
6. Additional Observations
The paper's Problem 5.3, proposing a "planted Strict-Weak Polymer" as a solvable proxy, is a well-motivated open problem that could catalyze follow-up work. The numerical evidence in Figure 2 that the Strict-Weak model closely approximates the Random Subsequence Model is compelling.
Generated Apr 9, 2026
Comparison History (122)
Paper 2 settles multiple open conjectures about the deletion channel—a longstanding problem in information theory—and introduces a novel spin glass framework connecting coding theory, combinatorics (longest common subsequence), and statistical physics. Its cross-disciplinary breadth, resolution of conjectures for all deletion probabilities p∈[0,1), and novel analytical tools (Random Subsequence Model) give it broader and deeper impact. Paper 1 makes solid contributions to finite-blocklength ISAC but addresses a more specialized, application-driven problem with less fundamental novelty.
Paper 1 resolves long-standing open conjectures regarding the deletion channel, a notoriously difficult foundational problem in information theory. By bridging statistical physics (spin glass models) with coding theory, it offers profound theoretical breakthroughs. While Paper 2 presents a strong applied advancement in neural compression, Paper 1's resolution of fundamental capacity limits and its broad interdisciplinary connections give it a higher potential for lasting, fundamental scientific impact.
Paper 2 demonstrates an unprecedented exponential and unbounded capacity gain in classical networks using quantum entanglement, shattering previous limits of under 6%. Its proven robustness to high levels of depolarizing noise makes it highly applicable to real-world quantum network development, offering broader transformative potential across the rapidly growing fields of quantum computing and telecommunications compared to the strictly theoretical, albeit impressive, channel capacity bounds solved in Paper 1.
Paper 1 demonstrates exponential and unbounded capacity gains from quantum entanglement assistance in classical multiple access channels—a fundamental and surprising result bridging quantum information and network information theory. The magnitude of gains (factors of 21-88x with small parameters) and robustness to noise make this practically significant. Paper 2 makes important contributions to deletion channel coding theory and spin glass models, settling conjectures about uniform codes. However, Paper 1's demonstration that quantum resources can provide exponential advantages in classical communication capacity is more paradigm-shifting, with broader implications across quantum computing, information theory, and communications.
Paper 2 likely has higher impact due to resolving a central open problem in information theory: proving uniformly-random codes achieve positive rate on the deletion channel for all p<1, including the hard regime p≥1/2, plus giving an analytic planted-model free energy yielding tight complementary bounds. It introduces a broadly connected spin-glass/subsequence framework linking coding theory, LCS, and statistical physics, suggesting cross-field uptake. Paper 1 is technically strong and novel for fault-tolerant quantum computing (transversal CCZ with sublinear Z-stabilizer generators), but its impact is more specialized and incremental relative to the wider and more definitive consequences of Paper 2.
Paper 2 settles multiple open conjectures about the deletion channel capacity under uniform codes, introduces a novel spin glass model connecting coding theory, combinatorics (LCS problem), and statistical physics, and provides tight bounds on a longstanding open problem. Its cross-disciplinary impact (information theory, probability, statistical physics) and resolution of concrete conjectures give it broader and more immediate scientific impact. Paper 1 makes strong technical contributions to quantum error correction with transversal gates, but addresses a more specialized audience within quantum coding theory.
Paper 1 solves longstanding theoretical conjectures regarding the capacity of the deletion channel and establishes deep connections between information theory and statistical physics. While Paper 2 offers practical engineering advancements for 6G networks, Paper 1's fundamental breakthroughs on a classic, historically intractable problem will likely have a broader and more enduring theoretical impact across multiple disciplines.
Paper 2 introduces a highly novel interdisciplinary framework linking statistical physics and information theory. By connecting spin glass models to the deletion channel, it not only settles multiple conjectures but also provides broad applicability across physics, computer science, and coding theory. While Paper 1 solves a significant 70-year-old open problem, its impact is largely confined to classical algebraic coding theory, whereas Paper 2 offers broader methodological innovation and cross-disciplinary impact.
Paper 2 resolves longstanding open conjectures in information theory regarding the deletion channel and establishes deep connections to statistical physics and spin glass models. While Paper 1 is highly timely and relevant to modern LLM optimization, Paper 2 provides foundational theoretical breakthroughs that span multiple classical disciplines, likely ensuring a more enduring and fundamental scientific legacy.
Paper 2 solves longstanding conjectures in information theory regarding the deletion channel and establishes deep connections between statistical physics (spin glasses) and coding theory. Its rigorous theoretical breakthroughs and exact analytic formulas provide a profound, cross-disciplinary impact, whereas Paper 1 presents a domain-specific, albeit practical, architectural improvement for wireless communications.