REVIEW 2 major objections 4 minor 19 references
Linear List Decodable Edit-Correcting Codes with Rate Approaching $1$
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read For any small fraction $\eta$ of insertions and deletions, there is a linear list decodable code with rate $1-O(\eta^{1/4})$ and polynomial-time encoding and decoding.
desk verdict A clever construction that may break the rate-1/2 barrier for linear list-decoding of edits, but a likely list-recovery convention mismatch in the imported theorem puts the central claim in doubt. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a $(\delta,l,L)$-sync sequence: matrices $S_1,\dots,S_n \in F_2^{a\times b}$ with full row rank such that the edit-distance balls $B(\operatorname{Row} S_{k_i}\setminus\{0\}, \delta b)$ of any $l+1$ distinct row spaces are disjoint, and each $S_i$ is itself $(\delta,L)$-list decodable. This condition generalizes the natural alignability condition that row spaces be pairwise disjoint, which has rate at most $1/2$; by instead requiring only that any $l+1$ row spaces have disjoint edit balls, the inner-code rate becomes $a/b = 1 - 2/(l+1) - 5H(\delta)$, approaching $1$ as $l$ increases. The construction of sync sequences uses a small-bias generator applied to $(l+1)$-wise independent seeds, with a Vazirani XOR-Lemma argument showing that the failure probability is polynomially small, and a polynomial-time verification procedure makes the construction deterministic. The sequence is the load-bearing mechanism that lets the decoder align received blocks to at most $l$ positions and bound the number of candidates per box before outer list recovery.
What would settle it
Take a small explicit instance (e.g., $n=2^6$, $\gamma=1/8$, so $\eta=1/64$), build the generator matrix, and run a randomized search over adversarial edit patterns of weight at most $\eta b n$; the theorem is false if any pattern yields a received string with more than $L_0$ codewords within edit distance, or if the decoder's output list omits the original codeword.
Extended reading notes
Core claim
The central claim is that linear list decodable codes can correct a fraction of insertions and deletions with rate approaching $1$, breaking the $1/2$ rate barrier that holds for unique linear edit correction. The proof works by a two-level concatenation: an outer $F_2$-linear list-recoverable code of rate $1 - c_1\sqrt{2\gamma}$ is folded to alphabet size $2^a$, and each symbol $c'_i$ is then encoded as $c'_i S_i$ using a $(\delta,l,L)$-sync sequence of matrices $S_i \in F_2^{a\times b}$. The sync condition, which says that the edit-distance balls of the row spaces of any $l+1$ distinct matrices are disjoint, replaces the stricter pairwise-disjointness condition that would force inner rate at most $1/2$; with the relaxed condition the inner rate is $a/b \geq 1 - 2/(l+1) - 5H(\delta)$, which approaches $1$ as $l$ grows. The decoder scans length-$b$ windows of the received string, inserts all plausible inner symbols into boxes, truncates boxes that grew too large, and then runs the outer list-recovery algorithm, producing a list that provably contains the transmitted codeword. The theorem states that for $0<\eta<1/64$ the resulting rate is $1-O(\eta^{1/4})$ with the stated triple-exponential list size.
Load-bearing premise
The load-bearing premise is that the external outer codes truly recover a message from a small list of candidate symbols at each position while losing only $O(\sqrt{\epsilon})$ of their rate; if their promised performance is weaker than claimed, the final rate and list size would change, though the concatenation strategy would survive.
Editorial extensions
If this is right
- For any fixed fraction of edits $\eta$, the rate can be made arbitrarily close to $1$ by choosing $\eta$ small, at the cost of larger list size and block length.
- The half-Singleton bound $R \leq (1-\delta)/2$ for linear codes applies only to unique decoding; with list decoding the rate can be $1-O(\eta^{1/4})$ even when correcting an $\eta$ fraction of edits.
- The encoder and decoder are polynomial-time and deterministic, so the gain in rate does not require random coding or super-polynomial decoding effort.
- The outer list-recoverable code is the bottleneck for the list size; improving that building block would immediately improve the list-size exponent of the final code.
- The construction is fully linear over $F_2$, so the code can be represented by a generator matrix and combined with other linear operations such as linear network coding.
Reading between the lines
- A natural next step is to determine the optimal tradeoff for linear list-decodable edit codes; the paper's rate $1-O(\eta^{1/4})$ may not be tight, and a matching lower bound would be a natural extension.
- The sync-matrix technique is not specific to insertions and deletions; the same relaxed-intersection idea could be adapted to other channels where unique linear decoding has a rate barrier, such as burst errors or tandem duplications.
- If an outer list-recoverable code with rate $1-O(\varepsilon)$ and list size polynomial in $1/\varepsilon$ were found, the same concatenation would yield linear list-decodable edit codes with rate $1-O(\eta^{1/2})$ and poly-sized lists; the current triple-exponential list size is an artifact of the outer code, not of the sync-matrix construction.
- The construction could be tested empirically at moderate block lengths to see how the actual rate and list size behave for finite $n$, since the hidden constants may be large before the asymptotics kick in.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs explicit binary linear codes that are list-decodable from a fraction η of edit errors with rate 1-O(η^{1/4}) and list size exp(exp(exp(O_η(log* n)))). The construction concatenates an outer high-rate list-recoverable code (from Hemenway–Ron-Zewi–Wootters) with an inner 'sync matrix sequence': each outer symbol is encoded by a distinct linear map S_i, and the matrices are chosen so that any received window can be attributed to only a few blocks, while each block is itself a list-decodable linear code. The decoder scans windows, fills candidate boxes, prunes oversized boxes, and invokes outer list recovery. If the cited outer codes use the same convention as Definition 3, the main theorem gives the first rate-1 linear list-decodable insdel codes, breaking the unique-decoding half-rate barrier for linear edit correction.
Significance. This is a strong theoretical contribution. The sync-matrix construction is novel, the code is fully explicit, the encoder and decoder are polynomial-time, and the list size is sub-polynomial for fixed η. The result would be a substantial advance over the half-Singleton bound for linear edit-correcting codes, and the paper clearly explains the intuition behind the construction. The machine-checkable parts are not present, but the proofs are largely self-contained except for the imported list-recoverable code theorem.
major comments (2)
- [§4.1, Lemma 15] The stated success probability in Lemma 15 is not derived. In the proof of Condition 1, the display following Eq. (1) gives Pr[1) fails] ≤ n^{l+1} 2^{(δ-1)b+l+2} ≤ n^{l+1} 2^{-0.5b+l+2}. With b ≥ 4(l+1) log n, this is 2^{l+2} n^{-(l+1)}, which for large n is much larger than the claimed n^{-(l+1)2^{l+2}}; the final inequality is algebraically false. A valid bound is O(n^{-(l+1)}) plus the 2n^{-7} term, which is still <1 for sufficiently large n and therefore suffices for the existence argument in Corollary 16, but the lemma as stated must be corrected.
- [§5, instantiation of Theorem 17] The correctness of the outer list-recovery step depends on Theorem 17 being (ε,l0,L0)-list recoverable in the sense of Definition 3, i.e., at most ε fraction of disagreements. The manuscript quotes Theorem 17 without stating the convention used in [18]. If [18] uses the alternative agreement-fraction convention (codewords must agree with the input lists on at least εN positions), then instantiating ε=2γ would guarantee only agreement ≥2γ, which is far weaker than the (1-2γ) agreement needed in Theorem 18, and the main rate claim would collapse. The authors must state the convention explicitly and confirm that the parameter match is with Definition 3.
minor comments (4)
- [§3, Lemma 11] The definition of L is garbled by the binomial-coefficient typesetting; it should read L = 2^{2/ε+1}, as used in the proof.
- [§4, Lemma 13 proof] The phrase 'Take b and 2^{l+1} to be the n and ϵ in Lemma 11' appears to be a typo: to obtain L = 2^{l+2} one must take ε = 2/(l+1), not ε = 2^{l+1}.
- [§5, parameter l0] The definition of l0 is typeset as inom{L(γ)}{γ^3}; it should be ⌈L(γ)/γ^3⌉ (a ceiling), as used in the proof of Theorem 18.
- [References] References [8] and [19] both refer to the same paper by Guruswami and Wang; one of the two citations should be removed or replaced.
Circularity Check
No significant circularity: the construction is self-contained apart from an external list-recovery code from non-overlapping authors.
full rationale
The paper's derivation chain does not fit any of the flagged circularity patterns. The rate and list-size claims are obtained by concatenating a deterministic inner sync-matrix sequence (Lemmas 13 and 15) with an outer F_q-linear list-recoverable code imported from Hemenway, Ron-Zewi, and Wootters [18, Theorem A.1], whose authors do not overlap with the current paper. No parameter is fitted to the target edit-correction quantity and then repackaged as a prediction: the inner code parameters (delta = 4 gamma, l = ceil(1/gamma) - 1, R = 1 - 2/(l+1) - 5H(delta)) and the outer code parameter (epsilon = 2 gamma) are chosen a priori, and Theorem 18 then proves correctness from the (4 gamma, l, L)-sync property and the (2 gamma, l0, L0)-list-recoverability property. Lemma 11 and Lemma 15 are self-contained probabilistic arguments, and the only external dependencies (small-bias generators from [14], list-recoverable codes from [18], and the similar window method in [19]) are not self-citations. The potential concern raised in the skeptic's headline, namely that Theorem 17's parameter epsilon may denote a minimum agreement fraction rather than a maximum disagreement fraction under Definition 3, is a parameter-convention incompatibility that could affect correctness of the instantiation, but it is not a circularity: the claimed result does not reduce to its inputs by construction. Accordingly, the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math Explicit eps-biased generators exist with seed length O(log n + log(1/eps)) (Lemma 8, [14]).
- standard math Vazirani's XOR lemma: an eps-biased distribution over F_2^m is eps*2^(m/2)-close to uniform (Lemma 9, [15]).
- standard math There exist (l+1)-wise independent random variables over F_2^phi generated with O(l*phi + log n) bits ([17] Corollary 3.34).
- domain assumption Theorem 17 ([18] Theorem A.1): deterministic poly-time F_q-linear list-recoverable codes with rate 1-c1*sqrt(eps), list size exp(exp(exp(O_(eps,l0,q)(log* N)))), and alphabet size q >= l0^(Theta(1/sqrt(eps))).
Cite this review
Pith. "Pith review of Linear List Decodable Edit-Correcting Codes with Rate Approaching $1$." pith.science (2026). https://pith.science/paper/XCW7FHPO
@misc{pith2026250612193,
author = {Pith},
title = {Pith review of: Linear List Decodable Edit-Correcting Codes with Rate Approaching $1$},
year = {2026},
howpublished = {\url{https://pith.science/paper/XCW7FHPO}},
note = {Machine review of arXiv:2506.12193}
}
abstract
Linear codes correcting one deletions have rate at most $1/2$. In this paper, we construct linear list decodable codes correcting edits with rate approaching $1$ and reasonable list size. Our encoder and decoder run in polynomial time.
Reference graph
Works this paper leans on
-
[18]
Local list recovery of high-rate tensor codes and applications,
B. Hemenway, N. Ron-Zewi, and M. Wootters, “Local list recovery of high-rate tensor codes and applications,” SIAM Journal on Computing , vol. 49, no. 4, pp. FOCS17–157, 2019
work page 2019
-
[1]
Synchronization strings: codes for insertions and deletions ap- proaching the singleton bound,
B. Haeupler and A. Shahrasbi, “Synchronization strings: codes for insertions and deletions ap- proaching the singleton bound,” in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , 2017, pp. 33–46
work page 2017
-
[2]
Deterministic document exchange protocols, and almost optimal binary codes for edit errors,
K. Cheng, Z. Jin, X. Li, and K. Wu, “Deterministic document exchange protocols, and almost optimal binary codes for edit errors,” in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, 2018, pp. 200–211
work page 2018
-
[3]
Optimal document exchange and new codes for insertions and deletions,
B. Haeupler, “Optimal document exchange and new codes for insertions and deletions,” in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, 2019, pp. 334–347
work page 2019
-
[4]
On linear and cyclic codes for correcting deletions,
K. A. Abdel-Ghaffar, H. C. Ferreira, and L. Cheng, “On linear and cyclic codes for correcting deletions,” in 2007 IEEE International Symposium on Information Theory . IEEE, 2007, pp. 851–855
work page 2007
-
[5]
Efficient linear and affine codes for cor- recting insertions/deletions,
K. Cheng, V. Guruswami, B. Haeupler, and X. Li, “Efficient linear and affine codes for cor- recting insertions/deletions,” 2022
work page 2022
-
[6]
Explicit and efficient constructions of linear codes against ad- versarial insertions and deletions,
R. Con, A. Shpilka, and I. Tamo, “Explicit and efficient constructions of linear codes against ad- versarial insertions and deletions,” IEEE Transactions on Information Theory , vol. 68, no. 10, pp. 6516–6526, 2022
work page 2022
-
[7]
Linear insertion deletion codes in the high-noise and high-rate regimes,
K. Cheng, Z. Jin, X. Li, Z. Wei, and Y. Zheng, “Linear insertion deletion codes in the high-noise and high-rate regimes,” 2023
work page 2023
Show all 19 references
-
[8]
Deletion codes in the high-noise and high-rate regimes,
V. Guruswami and C. Wang, “Deletion codes in the high-noise and high-rate regimes,” IEEE Transactions on Information Theory , vol. 63, no. 4, pp. 1961–1970, 2017. 11
1961
-
[9]
Optimally resilient codes for list-decoding from insertions and deletions,
V. Guruswami, B. Haeupler, and A. Shahrasbi, “Optimally resilient codes for list-decoding from insertions and deletions,” in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , ser. STOC 2020. New York, NY, USA: Association for Computing Machinery, 202...
2020
-
[10]
Reed solomon codes against adversarial insertions and deletions,
R. Con, A. Shpilka, and I. Tamo, “Reed solomon codes against adversarial insertions and deletions,” IEEE Transactions on Information Theory , vol. 69, no. 5, pp. 2991–3000, 2023
2023
-
[11]
Optimal two-dimensional reed–solomon codes correcting insertions and deletions,
——, “Optimal two-dimensional reed–solomon codes correcting insertions and deletions,” IEEE Transactions on Information Theory , vol. 70, no. 7, pp. 5012–5016, 2024
2024
-
[12]
Random reed-solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets,
R. Con, Z. Guo, R. Li, and Z. Zhang, “Random reed-solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets,” 2024. [Online]. Available: https://arxiv.org/abs/2407.07299
2024 arXiv
-
[13]
Reed-solomon codes against insertions and deletions: Full-length and rate-1 /2 codes,
P. Beelen, R. Con, A. Gruica, M. Montanucci, and E. Yaakobi, “Reed-solomon codes against insertions and deletions: Full-length and rate-1 /2 codes,” 2025. [Online]. Available: https://arxiv.org/abs/2501.11371
2025 arXiv
-
[14]
Simple constructions of almost k-wise independent random variables,
N. Alon, O. Goldreich, J. H ˚ astad, and R. Peralta, “Simple constructions of almost k-wise independent random variables,” Random Structures & Algorithms , vol. 3, no. 3, pp. 289–304, 1992
1992
-
[15]
Three xor-lemmas—an exposition,
O. Goldreich, “Three xor-lemmas—an exposition,” Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kauf- man, Leonid Le...
2011
-
[16]
On the list-decodability of random linear codes,
V. Guruswami, J. Hastad, and S. Kopparty, “On the list-decodability of random linear codes,” in Proceedings of the forty-second ACM symposium on Theory of computing, 2010, pp. 409–416
2010
-
[17]
Pseudorandomness,
S. P. Vadhan et al., “Pseudorandomness,” Foundations and Trends® in Theoretical Computer Science, vol. 7, no. 1–3, pp. 1–336, 2012
2012
-
[19]
Deletion codes in the high-noise and high-rate regimes,
V. Guruswami and C. Wang, “Deletion codes in the high-noise and high-rate regimes,” IEEE Transactions on Information Theory , vol. 63, no. 4, pp. 1961–1970, 2017. 12
1961
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.