{"id":"9d99fe67-686b-437f-b474-9efec1d4541a","arxiv_id":"2506.15233","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New bounds and two constructions for variable packet-error codes, including an optimal repetition-based scheme for N=2T+1 packets.","lead":"This paper derives new lower bounds on the rate versus distortion trade-off for variable packet-error correcting codes, and gives two explicit code constructions that approach or meet those bounds. The results improve on the existing polytope-code scheme and settle the optimal trade-off for the smallest nontrivial number of packets, N=2T+1.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Optimality claim for Theorem II.4 is only proven at blocklength k=2T+1; Corollary II.1's alphabet-size condition fails for larger k, so (R,1-R) optimality is not established for the VPEC problem as defined.","rationale":"The paper's theorems appear internally correct. The construction in Theorem II.4 and its proof are sound: the majority-based decoder, Lemma IV.2, and Lemma IV.3 hold up under detailed checking, and the O(T^3) complexity analysis is consistent. The conditional Construction 1 on L-MDS codes is honestly stated as conditional, and the cited existence results are appropriate. The load-bearing issue I found concerns the scope of the optimality claim rather than the correctness of any proof. Corollary II.1's bound R≥1−D for N=2T+1 relies on the Diametric Theorem, which requires q≥2k(1−D)/3+2. For a fixed alphabet size q=4(T+2)/3, this holds only at blocklength k=2T+1, not for the blocklength-multiplied version of the construction or for arbitrary larger blocklengths. Therefore, the paper establishes that the rate-distortion pair (R,1−R) matches its bound at blocklength 2T+1, but it does not establish optimality in the sense of Definition II.1, where blocklength is existential. The reader's strongest_claim overstates the result by omitting the blocklength qualifier. Since the paper's own Remark II.3 is carefully scoped, the verdict should remain ACCEPT, but a clarification in the paper would remove ambiguity. The concrete test of searching for a counterexample for T=1, N=3, q=4, k=6 would settle whether the optimality failure for larger blocklengths is real or merely a proof gap.","tokens_in":22125,"tokens_out":33219,"duration_ms":315128,"concrete_test":"Search for a T-VPEC code with N=2T+1, alphabet size q=4(T+2)/3, and blocklength k>N that achieves rate R<1−D for some D in [0,T/(2T+1)]. For a concrete instance, take T=1, N=3, q=4, D=1/3, k=6. Use a computer search over linear or small nonlinear encoders f: {0,1,2,3}^6 → ({0,1,2,3}^3)^3 to see whether a code with per-packet rate R<2/3 (packet length <4) and distortion at most 1/3 under one packet error exists. If such a code exists, the optimality of (R,1−R) fails for arbitrary blocklength; if no such code exists up to the search limit, that supports extending the lower bound but does not prove it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Remark II.3 claims that for 0≤D≤T/(2T+1) and |Σ|≥4(T+2)/3, the Theorem II.4 code achieves the optimal rate-distortion trade-off. The supporting lower bound, Corollary II.1, applies only when q≥2k(1−D)/3+2, where k is the blocklength. For the construction in Theorem II.4 and Remark IV.4, k=m(2T+1) for arbitrary m. With the fixed alphabet size q=4(T+2)/3, the condition holds at k=2T+1 (for D=0) but fails for every m>1. Thus Corollary II.1 does not provide a converse for the blocklength-extended codes, nor for any other code of blocklength larger than 2T+1 over the same alphabet. Since Definition II.1 allows the blocklength to vary, the pair (R,1-R) is not shown to be optimal in the standard achievability sense; it is only shown to match the bound for codes of blocklength exactly 2T+1. The paper itself scopes the claim to k=N=2T+1 in Remark II.3, but the reader's strongest_claim drops this qualifier, and the abstract's 'optimal rate-distortion trade-off' could be read more broadly. This is a genuine gap if the intended claim is optimality for the T-VPEC problem rather than for a single blocklength.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies variable packet-error coding (VPEC), in which a source of blocklength k is encoded into N packets of equal rate R and the decoder must recover the source losslessly when no packets are corrupted and with erasure distortion at most D when at most T packets are adversarially corrupted. The main results are: (i) three lower bounds on the achievable rate-distortion trade-off, obtained from the Singleton bound, a pigeonhole/anticode argument invoking the Ahlswede-Khachatrian Diametric Theorem, and a linear-anticode dimension bound; (ii) Construction 1, which interleaves an L-MDS [N, rho N] code to produce a T-VPEC code of rate 1/(rho N) and distortion LT/N, conditional on the existence of the underlying L-MDS code; and (iii) Construction 2, a repetition-code variant for N=2T+1 that for every s<=T yields a T-VPEC code of rate 1-s/(2T+1) and distortion s/(2T+1), decodable in O(T^3) time, with blocklength k=m(2T+1) handled by m independent batch transmissions. For k=N=2T+1 and alphabet size at least 4(T+2)/3, Remark II.3 shows the pair (1-D,D) matches the lower bound from Corollary II.1, establishing optimality of the construction for this parameter regime. I verified that the optimality claim in the paper is explicitly scoped to k=N=2T+1; the paper does not claim a converse for the longer blocklengths in Remark IV.4.","tokens_in":22389,"tokens_out":27612,"duration_ms":253966,"significance":"The paper is a solid contribution to the VPEC literature. The lower bounds unify and slightly generalize the first part of [8, Theorem 1], and the second construction pins down the exact rate-distortion curve in the N=2T+1 case for a nontrivial alphabet-size range, a genuinely new result. The proofs are mostly elementary and transparent, with no fitted parameters: the only external ingredients are the Singleton bound, the Diametric Theorem, and the existence of higher-order MDS codes. Both constructions are compared with the polytope codes of [8] in explicit parameter regimes. One caveat is that Construction 1 is explicit only conditional on an [N, rho N] L-MDS code; explicit constructions are available for L=2 via [18], while for L>2 the paper cites existence results rather than giving a deterministic construction. This is stated transparently in Theorem II.3, so it does not affect the validity of the theorem, but it should be kept in mind when reading the word 'explicit' in the abstract.","major_comments":[],"minor_comments":[{"comment":"The optimality statement is proved only for blocklength k=N=2T+1; for the blocklength-extended codes in Remark IV.4 with k=m(2T+1), Corollary II.1 does not provide a converse because its alphabet-size condition q >= 2k(1-D)/3+2 grows with k. The abstract's phrase 'optimal rate-distortion trade-off' should be qualified accordingly, for example as 'for codes of length N=2T+1', to prevent an overbroad reading.","section":"Remark II.3 and Abstract"},{"comment":"The definitions of A_i and B_i appear to have missing complement bars: A_i should be the multiset of candidates from the packets that actually contain x_i, i.e., from the complement of S_{i-s+1}. In addition, Algorithm 2 sets 'xi2 = MFA1', which should read 'xi2 = MFA2'. Please correct these in the final version.","section":"Algorithm 2 and Lemma IV.3"},{"comment":"The Diametric Theorem is stated for integer d, but kD may be non-integral. The derivation should explicitly use d=floor(kD), or state that Dk is assumed integral, since the final bound (1-D)/(N-2T) then follows immediately.","section":"Proof of Corollary II.1"},{"comment":"In the distortion analysis, the sentence 'the remaining columns are those where all the outputted codewords agree with Y' should read 'agree with one another (and hence equal the transmitted codeword in those columns)'; agreement with the received word Y is not required and, in fact, the decoder only needs the agreed-upon symbols. The column-erasure accounting is unaffected.","section":"Proof of Theorem II.3"},{"comment":"For L>2, the underlying [N, rho N] L-MDS code is only known to exist for sufficiently large fields; the paper should state more explicitly that for these values of L the construction is conditional on existence, whereas for L=2 explicit constructions from [18] are available.","section":"Theorem II.3 and Remark II.1"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the central claims are appropriately scoped. I recommend minor revision to fix the notation and typos and to align the abstract's 'optimal' wording with the k=N=2T+1 statement. No concerns about novelty or fit: the paper extends [8] with new bounds and constructions, including a tight point on the trade-off."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's a quick read of arXiv:2506.15233. In short: the paper is solid, the math is careful, and it genuinely improves on the state of the art for VPEC. The one caveat to keep in mind is that the \"optimal rate-distortion trade-off\" in the abstract is only established for one blocklength, N=2T+1, not for the general T-VPEC problem with variable blocklength. The authors are careful about this in Remark II.3, but the abstract could mislead.\n\nWhat's new: Theorem II.2's anticode bound (Eq. 7) and the linear-code bound (Eq. 8) are genuinely new, and they imply the earlier bound from [8] as a special case. Construction 1 via L-MDS interleaving gives an explicit scheme that beats the polytope codes for a range of parameters, with field size polynomial in N for fixed T. Construction 2 is a nice combinatorial scheme achieving (1-s/(2T+1), s/(2T+1)) with O(T^3) decoding, and it matches the lower bound at blocklength exactly 2T+1. The proofs are clean; the anticode argument is a nice use of the Diametric Theorem, and the linear-code bound is a sensible specialization.\n\nSoft spots: The optimality claim in Remark II.3 is explicitly scoped to k=N=2T+1, and the supporting converse from Corollary II.1 needs q >= 2k(1-D)/3 + 2. For the m-fold extension in Remark IV.4, that condition fails for m>1 when the alphabet size is fixed. So the lower bound does not apply to the extended codes, and the pair (R,1-R) is not shown to be optimal for the general T-VPEC problem with arbitrary blocklength. This is a real limitation of the claim, but the paper itself largely stays within its scope. Construction 1 depends on existence of [N,rho N] L-MDS codes with the specific rho from (9); for L>2 the paper cites existence rather than giving deterministic constructions. That dependency is honestly flagged and is not a flaw, but it makes the achievable region conditional.\n\nCitation practice looks fair: the comparisons to [8] are concrete, the L-MDS background is properly attributed, and there are no fitted parameters or circular arguments. The slightly loose phrase in Construction 1 about \"each column contains exactly rho N information symbols\" is a simplification but the distortion accounting is valid.\n\nI'd bring this to our reading group and I'd cite the bounds and the repetition-based construction. It deserves a serious referee and should go out for review.","headline":"Solid VPEC paper with genuinely new bounds and constructions; the optimality claim is blocklength-specific and the abstract slightly oversells it.","tokens_in":22986,"tokens_out":2665,"would_cite":true,"duration_ms":27213,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B35","94A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"For 2T+1 parallel packet channels with up to T adversarial corruptions, a repetition-code variant achieves the optimal trade-off between packet rate and erasure distortion.","keywords":["variable packet-error coding","rate-distortion trade-off","erasure distortion","higher-order MDS codes","list decoding","repetition codes","adversarial packet errors","network coding"],"falsifier":"Exhaustively simulate the decoder of Construction 2 for a small case, such as $T = 2$ and $s = 1$ with $N = 5$, over every error pattern of size at most $T$ and all source messages; if any pattern yields more than $s$ erasures, Theorem II.4 would be false. For Theorem II.3, finding a parameter set $(N, T, L)$ that meets the hypotheses but for which no $[N, \\rho N]$ $L$-MDS code with $\\rho = 1 - (1+1/L)\\frac{T}{N}$ exists would falsify the claimed rate–distortion region.","tokens_in":21900,"feed_emoji":"📡","tokens_out":16142,"duration_ms":120673,"temperature":0.7,"pith_summary":"Variable packet-error coding (VPEC) asks for a code that sends a source over N parallel packet channels, tolerates up to T corrupted packets, and reconstructs the source losslessly when no corruption occurs, while keeping erasure distortion small when errors do occur. The paper proves new lower bounds on the achievable rate–distortion trade-off and gives two explicit constructions. The first construction uses higher-order MDS codes (L-MDS codes) with interleaving to beat the previously known polytope codes for general parameters. The second, a variant of the repetition code, is optimal when $N = 2T+1$: for any $s \\le T$ it gives per-packet rate $1 - \\frac{s}{2T+1}$ and distortion at most $\\frac{s}{2T+1}$, with decoding in $O(T^3)$ time. With the paper's lower bound, this shows the pair $(R, 1-R)$ is optimal for $2T+1$ packets when the alphabet is large enough.","feed_headline":"Optimal codes for variable packet errors hit rate-distortion bound","feed_subtitle":"A repetition-style scheme with O(T^3) decoding matches the proven lower bound for 2T+1 packets.","key_machinery":"The optimal construction is a variant of the repetition code: a message of $2T+1$ fragments is encoded into $2T+1$ packets, where packet $j$ contains all fragments except the $s$ consecutive fragments in a cyclic window. Each fragment therefore appears in $2T+1-s$ packets, so a majority vote recovers it when few packets are corrupted; when the vote is inconclusive, a pairing lemma (Lemma IV.2) guarantees two unresolved indices with cyclic separation in $\\{s, \\ldots, 2T+1-s\\}$, and the decoder compares frequency counts in the two corresponding packets to decide which fragment to trust and which to erase. The general-parameter construction instead interleaves an $L$-MDS code $N$ times; its $(T,L)$-list decodability keeps at most $L$ candidate codewords after a $T$-error pattern, and erasing columns where candidates disagree costs at most $\\frac{LT}{N}$ distortion.","core_discovery":"For any alphabet, positive integers $T$ and $s \\le T$, and blocklength $k$ divisible by $2T+1$, there exists a $T$-VPEC code with $N = 2T+1$ packets, per-packet rate $R = 1 - \\frac{s}{2T+1}$, and erasure distortion at most $D = \\frac{s}{2T+1}$ under up to $T$ packet errors; decoding runs in $O(T^3)$. The code is built by partitioning the message into $2T+1$ fragments and having each packet carry all fragments except a cyclic block of $s$ of them. Together with the lower bound of Corollary II.1, this makes the rate–distortion pair $(R, 1-R)$ optimal for $0 \\le D \\le \\frac{T}{2T+1}$ whenever the alphabet size is at least $\\frac{4(T+2)}{3}$.","pith_inferences":["The cyclic-omission structure of Construction 2 is a special balanced design; generalizing it to other designs may yield optimal codes for $N \\ne 2T+1$ or for channels with different per-packet rates, which the paper leaves open.","The $O(T^3)$ decoding time makes the optimal scheme computationally plausible; an empirical test against adversarial erasure patterns for small $T$ would directly confirm the distortion guarantee and the majority-vote logic.","Optimality here is proven only for alphabets with $|\\Sigma| \\ge \\frac{4(T+2)}{3}$; whether the same trade-off is achievable over smaller alphabets, including the binary case, is a natural open question suggested by the paper's own bounds."],"forward_implications":["With $N = 2T+1$ packets, the rate–distortion pair $(R, 1-R)$ is achievable for $\\frac{T+1}{2T+1} \\le R \\le 1$ and is optimal in the range $0 \\le D \\le \\frac{T}{2T+1}$ when the alphabet has size at least $\\frac{4(T+2)}{3}$.","The MDS-based construction achieves strictly better rate–distortion points than polytope codes for $N \\ge F(T)+1$ and $T \\ge 4(L+1)$, and for $L=2$ it needs only a finite field of size polynomial in $N$ for fixed $T$, rather than the real alphabet used by polytope codes.","The lower bounds in Theorem II.2 recover the known bound $R \\ge \\frac{1}{N-T}$ for $0 \\le D \\le 1$ and $R \\ge \\frac{1}{N-2T}$ for $D=0$, and via the Diametric Theorem give a closed form $R \\ge \\max\\{(1-D)/(N-2T), 1/(N-T)\\}$ for large alphabets.","In the asymptotic regime with fixed error fraction $\\theta = T/N$ and $N \\to \\infty$, the $L$-MDS construction achieves a strictly better overall rate–distortion curve than classical MDS codes whenever $\\theta \\le 1/(L+1)$."],"supporting_citations":[{"why":"Introduces the adversarial-channel setting that VPEC generalizes and shows source–channel separation is not optimal.","marker":"[7]"},{"why":"Defines the T-VPEC problem, provides the polytope-code construction, and gives the achievability bounds that the new constructions improve on.","marker":"[8]"},{"why":"Introduces higher-order MDS codes and the list-decoding bound that Construction 1 relies on.","marker":"[18]"},{"why":"States the Diametric Theorem, which yields the anticode size used in Corollary II.1.","marker":"[32]"},{"why":"Is the prior result on interleaved-code list decoding that Proposition IV.1 refines.","marker":"[33]"},{"why":"Shows existence of higher-order MDS codes over large fields, supplying the code for Construction 1.","marker":"[34]"},{"why":"Provides the majority-vote subroutine used to find the most frequent element, giving O(T^3) decoding.","marker":"[38]"}],"fun_headline_variants":["Variable packet-error codes hit optimal rate-distortion","Optimal rate-distortion for variable packet-error coding","Repetition-style code achieves optimal rate-distortion","New bounds and constructions for variable packet-error coding","Optimal packet-error codes with O(T^3) decoding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The improved general-parameter construction (Construction 1) assumes the existence of an $[N, \\rho N]$ $L$-MDS code over a sufficiently large field with $\\rho = 1 - (1+1/L)\\frac{T}{N}$, which the paper does not explicitly construct for $L > 2$; the optimal repetition-based construction makes no such assumption.","fun_headline_variants_meta":{"raw":{"variants":["Variable packet-error codes hit optimal rate-distortion","Optimal rate-distortion for variable packet-error coding","Repetition-style code achieves optimal rate-distortion","New bounds and constructions for variable packet-error coding","Optimal packet-error codes with O(T^3) decoding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000196,"raw_usage":{"total_tokens":1326,"prompt_tokens":877,"completion_tokens":449,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":373}},"tokens_in":493,"tokens_out":449,"duration_ms":4421,"temperature":1.0,"reasoning_tokens":373,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:45:08.803084+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively simulate the decoder of Construction 2 for a small case, such as $T = 2$ and $s = 1$ with $N = 5$, over every error pattern of size at most $T$ and all source messages; if any pattern yields more than $s$ erasures, Theorem II.4 would be false. For Theorem II.3, finding a parameter set $(N, T, L)$ that meets the hypotheses but for which no $[N, \\rho N]$ $L$-MDS code with $\\rho = 1 - (1+1/L)\\frac{T}{N}$ exists would falsify the claimed rate–distortion region.","supporting_citations":[{"cited_title":"Coding for the Large-Alphabet Adversarial Channel,","cited_arxiv_id":null,"evidence_quote":"Introduces the adversarial-channel setting that VPEC generalizes and shows source–channel separation is not optimal."},{"cited_title":"Variable Packet-Error Coding,","cited_arxiv_id":null,"evidence_quote":"Defines the T-VPEC problem, provides the polytope-code construction, and gives the achievability bounds that the new constructions improve on."},{"cited_title":"Higher-Order MDS Codes,","cited_arxiv_id":null,"evidence_quote":"Introduces higher-order MDS codes and the list-decoding bound that Construction 1 relies on."},{"cited_title":"The Diametric Theorem in Hamming Spaces-Optimal Anticodes,","cited_arxiv_id":null,"evidence_quote":"States the Diametric Theorem, which yields the anticode size used in Corollary II.1."},{"cited_title":"List decoding tensor products and interleaved codes,","cited_arxiv_id":null,"evidence_quote":"Is the prior result on interleaved-code list decoding that Proposition IV.1 refines."},{"cited_title":"Generic Reed-Solomon Codes Achieve List-decoding Capacity,","cited_arxiv_id":null,"evidence_quote":"Shows existence of higher-order MDS codes over large fields, supplying the code for Construction 1."},{"cited_title":"MJRTY-A Fast Majority V ote Algorithm,","cited_arxiv_id":null,"evidence_quote":"Provides the majority-vote subroutine used to find the most frequent element, giving O(T^3) decoding."}],"review_version":1}