{"id":"358cf18a-ac24-47d9-89c9-86762681ec91","arxiv_id":"2502.05858","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Alphabet-permutation codes achieve the optimal list-recovery tradeoff of random codes with only polynomially many random bits.","lead":"This paper introduces alphabet-permutation codes, built by repeatedly shuffling the alphabet at every coordinate. They match the mistake-fixing performance of fully random codes while using far fewer random bits, previously impossible for any structured code family.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2.6's proof of Eq. (4) requires η ≥ 2 log_q(2nk/ln2)/n, not the stated 2 log_q(2n/ln2)/n, when k>n; Theorem 1.1's proof is therefore incomplete for its stated η range.","rationale":"The reader identified the [AL13] total-variation bound as the weakest assumption. That bound is likely correct (indeed Alon–Lovett give O(δ), so the stated O(δ q^{4m}) is a conservative overestimate) and does not threaten the central claim. The actual gap is the η condition in Proposition 2.6/Theorem 1.1. The stated lower bound on η is insufficient when k>n, which occurs for q>2 at rates near capacity; the proof's Eq. (4) induction fails. The final parameter setting η=2 log_q(nk)/n escapes this, so the main existence result (polynomial-randomness AP codes achieving the Elias bound) is likely correct, but the theorem's stated assumptions and proof need revision. Hence CONDITIONAL rather than ACCEPT or REJECT.","tokens_in":14422,"tokens_out":32046,"duration_ms":286231,"concrete_test":"Check the final step of the proof of Eq. (4) in Proposition 2.6 by substituting q=256, n=1000, ℓ=1, ρ=0.01, L=10, and η=2 log_q(2n/ln2)/n. Compute k=R·n·log2 q; verify k/n>1 and k·2·q^{−ηn/2}>ln2, so the inequality exp(...)≤2 fails. Then repeat with η=2 log_q(nk)/n; the exponent becomes ≤2/n, well below ln2, confirming that the proof works only for the stronger condition.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Proposition 2.6 (and hence Theorem 2.13 and Theorem 1.1, which invoke it) has a gap in the proof of Eq. (4). The induction for λ_i needs λ_k ≤ 2^{k+1}λ0, and the penultimate step uses exp(k·2·q^{−ηn/2}) ≤ 2. Equation (1) only gives q^{−ηn/2} ≤ ln2/(2n), making the exponent at most k·ln2/n. Since k = R·n·log2 q and R can be close to 1 for large q and small ρ (e.g., q=256, ρ=0.01 gives R≈0.97, k≈7.7n), k/n need not be ≤1; the exponent can exceed ln2, so the claimed bound λ_k ≤ 2^{k+1}λ0 does not follow. The fix is to require η ≥ 2 log_q(2nk/ln2)/n; this is exactly the scale of the parameter choice 'η = 2 log_q(nk)/n' made after Theorem 1.1. Thus the announced high-probability construction is plausibly correct, but the theorem as stated (for all η satisfying the weaker bound) is not established by the proof in the manuscript.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces alphabet-permutation (AP) codes, a family of codes generated by iteratively applying random coordinate-wise permutations to an initial word. The main result (Theorem 1.1) states that when the permutations are drawn from an approximately ℓ-wise independent distribution, the resulting random code ensemble is (ρ, ℓ, L)-list-recoverable with high probability, at rate R = 1 - h*_{q,ℓ}(ρ) - (log_q binom(q,ℓ)+1)/(n(L+1)) - η, using only O(n^2 log q (ℓ log q + log n)) random bits. This matches the list-recovery performance of plain random codes while being neither linear nor additive, and the paper argues this is the first such structured, randomness-efficient construction. The technical core is a potential-function argument showing that a B-mixing permutation distribution ensures small intersections with all bad sets.","tokens_in":14700,"tokens_out":39058,"duration_ms":348810,"significance":"If the proof is repaired, this is a significant contribution: it shows that the list-recovery Elias bound can be achieved by a family of codes that are simultaneously structured and polynomial-time samplable, in contrast to plain random codes which need exponentially many bits. The claimed exponential improvement in list size over linear and additive codes is striking and would answer a natural open question. The potential-function framework is elegant and likely to be reusable. The use of known derandomization tools (KNR09, AL13) is appropriate, and the paper is careful about multiset semantics and rate accounting. However, the proof as written contains a rate-definition inconsistency and a gap in a key exponential estimate; these are local and likely fixable, but they currently block the stated claims.","major_comments":[{"comment":"The rate parameter R is defined inconsistently. Proposition 2.6 defines R := k/n · log_2 q, and Corollary 2.7 and Theorem 2.13 repeat this. However, the proof's identity 2^{k+1} λ0 = 2 q^{n(α+β−1+R)} requires q^{nR} = 2^k, which holds for R = k/(n log_2 q) (the q-ary rate), not for R = (k/n) log_2 q. For q > 2, the printed definition gives q^{nR} = 2^{k (log_2 q)^2}, so the rate condition R = 1 − β − ... − η cannot hold while R is the intended q-ary rate close to 1. Theorem 1.1's definition k = R · log_2 q · n is consistent with the corrected R = k/(n log_2 q). Please correct the definition of R in Proposition 2.6, Corollary 2.7, and Theorem 2.13, and verify that all subsequent algebra uses the corrected quantity.","section":"§2.5 (Proposition 2.6), §2.7 (Theorem 1.1)"},{"comment":"The proof of λ_k ≤ 2^{k+1} λ0 contains a too-loose exponential estimate. The displayed chain bounds the exponent by i · 2^{i/2+1} · λ0^{1/2} ≤ k · 2 · q^{−ηn/2} and then requires exp(k · 2 · q^{−ηn/2}) ≤ 2. Equation (1) only yields q^{−ηn/2} ≤ ln2/(2n), so this step forces k ≤ n. For the intended parameters in Theorem 1.1, k = R n log_2 q can exceed n by a factor of log_2 q. The gap is repairable: using the sharper bound Σ_{j=0}^{i-1} 2^{j/2} = O(2^{i/2}) gives an exponent of size O(2^{k/2} λ0^{1/2}) = O(q^{−ηn/2}), since 2^{k/2} λ0^{1/2} = q^{−ηn/2} under the corrected rate definition, and Eq. (1) then suffices. As written, however, the proof of Proposition 2.6 (and hence of Theorem 1.1) is incomplete for the stated η range.","section":"§3, Eq. (4)"}],"minor_comments":[{"comment":"The notation |B| is used both for the number of sets in the family B (in the rate formula) and for the cardinality of an individual set B ∈ B (in Claim 3.3). Please disambiguate, for example by writing |B| for the family size and |B|_set or vol(B) for set cardinality.","section":"§2.5, §3"},{"comment":"The step 'π_i(Z_i) is uniformly distributed over binom(Σ,ℓ)' follows from ℓ-wise independence, but it would help to spell out the argument: apply the definition to an arbitrary ordering of Z_i and then quotient by the symmetric group on the tuple.","section":"§2.6, Lemma 2.12"},{"comment":"Theorem 2.18 is a load-bearing black box. Please state it with the precise theorem number in [AL13] and its exact hypotheses, so that the O(δ q^{4ℓ}) dependence and any restrictions on q and ℓ can be verified by the reader.","section":"§2.7, Theorem 2.18"},{"comment":"The line 'taking B′ := f^{-1}(B)' and then asserting B′ is uniform over B deserves an explicit justification: condition 1 of B-mixing makes the map B ↦ f(B) an injection from the finite family B to itself, hence a bijection, and condition 2 then yields uniformity of the preimage. Adding this sentence would prevent a potential misunderstanding.","section":"§3, Claim 3.4"}],"recommendation":"major_revision","confidential_remarks":"Both major issues appear to be fixable without changing the main construction or the claimed parameters: the rate definition should be R = k/(n log_2 q), and the exponential estimate in Eq. (4) can be sharpened via a geometric-series bound. I therefore view this as a major revision rather than a rejection. The referee report is not a challenge to the novelty or significance, which seem appropriate. The authors should also double-check that the cited [AL13] bound, as used in Theorem 2.18, indeed gives the stated O(δ q^{4ℓ}) total-variation distance for m-wise δ-independent permutations over alphabets of size q."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: this is the first construction I've seen that matches the Elias list-recovery bound with a structured, polynomial-randomness code, and the B-mixing/potential proof is a real technique. The paper is worth serious refereeing; the only substantive issue I found is a repairable gap in the proof of Eq. (4) in Proposition 2.6.\n\nWhat's new: alphabet-permutation codes, defined by iterating random coordinate-wise permutations. The B-mixing abstraction cleanly reduces list-recovery to a potential function, and the recurrence E[K_i] ≤ K_{i-1}^2 plus the deterministic lower bound K_i ≥ 1+2β is elegant. The special case recovering RACs/RLCs is a nice sanity check. The result beats the known lower bounds for linear/additive families, so the contribution is real.\n\nSoft spots: the stress-test note is correct. In the induction proving λ_k ≤ 2^{k+1} λ0, the step 'exp(k·2·q^{-ηn/2}) ≤ 2' uses only q^{-ηn/2} ≤ (ln 2)/(2n) from the theorem's η bound. Since k = R n log2 q can be > n (e.g., q=256, R≈0.97 gives k≈7.7n), the exponent can be ~5.5, so the bound fails. The fix is to strengthen the η condition to 2 log_q(2nk/ln2)/n. The paper's eventual choice η = 2 log_q(nk)/n satisfies this, so the main theorem's application is fine; it's the statement as written with the weaker η that is not proven. Also, the reliance on [AL13] for the TV bound O(δ q^{4m}) is black-box, but that's a standard tool and not a red flag. The rest of the potential argument checks out.\n\nBottom line: this paper makes a genuine advance and the proof is largely solid, with one clear technical repair. I'd send it to a good referee and expect it to come back in acceptable shape after the η fix.","headline":"Genuinely new AP-code construction matching the Elias list-recovery bound with polynomial randomness; the main proof has a repairable gap in the η condition for Eq. (4), but the advertised parameter setting survives.","tokens_in":15264,"tokens_out":4015,"would_cite":true,"duration_ms":37323,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B65","94B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Alphabet-permutation codes match plain random codes' list-recovery guarantees.","keywords":["alphabet-permutation codes","list-recoverability","list-decoding","Elias bound","randomness-efficient codes","m-wise independent permutations","non-additive codes","derandomization"],"falsifier":"For a concrete choice such as $q=4$, $\\ell=2$, sample the [KNR09] permutation family, compute the minimum total variation distance from its uniform distribution to any truly 2-wise independent distribution; if that minimum exceeds the constant $c\\,\\delta q^{4\\ell}$ used in Theorem 1.1, the transfer step fails and the claimed failure bound has no basis.","tokens_in":14191,"feed_emoji":"🔀","tokens_out":12483,"duration_ms":111240,"temperature":0.7,"pith_summary":"This paper introduces alphabet-permutation (AP) codes, built by starting from a fixed word and applying coordinate-wise permutations chosen by the input bits. It claims that when the permutations come from a sufficiently mixing distribution — in particular, from a nearly $\\ell$-wise independent family — the resulting random code is almost surely $(\\rho,\\ell,L)$-list-recoverable at rate $1-h^*_{q,\\ell}(\\rho)-\\varepsilon$ with list size $L=O(\\ell/\\varepsilon)$. That matches the guarantee of plain random codes while using only polynomially many random bits instead of exponentially many, and the codes are neither linear nor additive. Because separate lower bounds force linear and additive families to have exponentially larger list sizes, the construction shows that the random-code benchmark for list recovery is compatible with nontrivial structure.","feed_headline":"Match random codes' list-recovery with polynomial randomness","feed_subtitle":"A non-linear, non-additive code family reaches the Elias list-recovery bound without exponential random seeds","key_machinery":"The engine is the B-mixing condition: a distribution over coordinate-wise maps such that for every bad set $B \\in \\mathcal{B}_{\\rho,\\ell}$ — a cluster of words that agree with a fixed list-tuple except on at most $\\rho n$ coordinates — the image $f(B)$ under the map is uniform over the whole family $\\mathcal{B}_{\\rho,\\ell}$. Proposition 2.6 shows that if the power ensemble $\\mathcal{D}^n$ is B-mixing, a random AP code of the stated rate avoids all bad sets with failure probability at most $\\sqrt{2}\\,k\\,q^{-\\eta n/2}$; the proof tracks the potential $K_C = \\mathbb{E}_{B \\sim U(\\mathcal{B})} q^{\\alpha n |C \\cap B|}$ and shows $\\mathbb{E}[K_{C_i} \\mid C_{i-1}] \\leq K_{C_{i-1}}^2$, with $K_C < 2$ forcing $|C \\cap B| \\leq L$ for every bad set. Lemma 2.12 shows that $\\ell$-wise independent permutations are B-mixing, Theorem 2.17 (cited to [KNR09]) supplies small $\\ell$-wise $\\delta$-independent families, and Theorem 2.18 (cited to [AL13]) converts near-independence to true independence with total-variation error $O(\\delta q^{4\\ell})$, which yields the polynomial random-bit count.","core_discovery":"The paper's central claim is Theorem 1.1: for $q \\geq 2$, $\\ell < \\min\\{q,L\\}$, $0 \\leq \\rho \\leq 1-\\ell/q$, and parameters $\\eta,\\delta$ as stated, there is a random AP-code ensemble of rate $R = 1-h^*_{q,\\ell}(\\rho) - \\frac{\\log_q \\binom{q}{\\ell}+1}{n(L+1)} - \\eta$ that fails to be $(\\rho,\\ell,L)$-list-recoverable with probability at most $\\sqrt{2}\\,k\\,q^{-\\eta n/2} + c\\,\\delta\\,n\\,k\\,q^{4\\ell}$, and the ensemble can be sampled from an $\\ell$-wise $\\delta$-independent permutation family using $O(nk(\\ell \\log q + \\log 1/\\delta))$ random bits. With $\\eta,\\delta$ set as in the paper, this yields, with high probability, $(\\rho,\\ell,L)$-list-recoverable codes of rate $1-h^*_{q,\\ell}(\\rho) - \\frac{\\ell}{L+1}(1+o(1))$. The proof first establishes the guarantee for a truly $\\ell$-wise independent permutation distribution via a B-mixing potential argument, then transfers it to the cheaper near-independent family through a total-variation closeness bound. Since AP codes are not closed under addition, the additive/linear lower bounds cited in the paper do not constrain their list size, which the paper presents as the first structured, polynomial-randomness construction to match plain random codes.","pith_inferences":["If the total-variation bound in [AL13] could be improved beyond $O(\\delta q^{4\\ell})$, the same proof would immediately give smaller random-bit budgets or support larger list sizes $\\ell$; this is a natural target for follow-up work.","The potential-function proof only uses regularity of the bad-set family and an upper bound on set sizes, so the same scheme may yield randomness-efficient codes that avoid other structured families of bad sets, not only list-recovery clusters.","The explicit failure bound in Theorem 1.1 is testable: for small $q$, $\\ell$, $n$ one can sample the [KNR09] permutation family, build the AP code, and check list-recovery against random list-tuples to compare empirical failure rates with the theorem's prediction."],"forward_implications":["Any rate within a gap $\\varepsilon$ below the list-recovery capacity $1-h^*_{q,\\ell}(\\rho)$ is attained with list size $O(\\ell/\\varepsilon)$, matching plain random codes in the large-alphabet regime.","The construction uses only $O(n^2 \\log q \\cdot (\\ell \\log q + \\log n))$ random bits for the paper's parameter choices, replacing the exponential randomness of plain random codes.","The codes are neither linear nor additive, so the linear/additive lower bounds for list-recovery do not apply to them; the iterative permutation encoding is the structure that remains.","A special case with additive shifts over characteristic-two fields recovers random additive codes and binary random linear codes, placing their list-decodability in the same B-mixing framework."],"supporting_citations":[{"why":"Supplies the small $\\ell$-wise $\\delta$-independent permutation family used to sample the code's entries, giving the polynomial random-bit count.","marker":"[KNR09]"},{"why":"Gives the total-variation closeness between near-independent and truly independent permutations that transfers the list-recovery guarantee to the cheaper ensemble.","marker":"[AL13]"},{"why":"Provides the potential-function and combinatorial bounds for list decoding that the B-mixing argument adapts.","marker":"[GHSZ02]"},{"why":"Proves improved list-decodability of binary random linear codes, the special case whose generating-sequence analysis the paper generalizes.","marker":"[LW21]"},{"why":"Supplies the capacity function $h^*_{q,\\ell}(\\rho)$ and the size bounds on $(\\rho,\\ell)$-clusters used to set the rate and the bad-set family.","marker":"[Res20]"},{"why":"Establishes the near-optimal list-recovery lower bound for linear code families, the barrier the non-additive AP construction bypasses.","marker":"[LS25]"},{"why":"Shows random linear codes also suffer the large-list-size lower bound, reinforcing the need to leave additivity.","marker":"[LMS24]"}],"fun_headline_variants":["AP codes: random-code list recovery with polynomial randomness","Structured codes match random list-recovery using few random bits","Alphabet-permutation codes beat linear bounds on list size","Let's have both: optimal list-recovery without exponential seeds","New non-linear codes match random list recovery, use less randomness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole randomness saving rests on the theorem that any $m$-wise $\\delta$-independent permutation distribution is $O(\\delta q^{4m})$-close in total variation to a truly $m$-wise independent distribution; if that approximation degrades faster with $q$ or $m$ than stated, the advertised failure probability and random-bit count no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["AP codes: random-code list recovery with polynomial randomness","Structured codes match random list-recovery using few random bits","Alphabet-permutation codes beat linear bounds on list size","Let's have both: optimal list-recovery without exponential seeds","New non-linear codes match random list recovery, use less randomness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000602,"raw_usage":{"total_tokens":2851,"prompt_tokens":1026,"completion_tokens":1825,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":642,"completion_tokens_details":{"reasoning_tokens":1741}},"tokens_in":642,"tokens_out":1825,"duration_ms":10629,"temperature":1.0,"reasoning_tokens":1741,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T17:41:07.995948+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a concrete choice such as $q=4$, $\\ell=2$, sample the [KNR09] permutation family, compute the minimum total variation distance from its uniform distribution to any truly 2-wise independent distribution; if that minimum exceeds the constant $c\\,\\delta q^{4\\ell}$ used in Theorem 1.1, the transfer step fails and the claimed failure bound has no basis.","supporting_citations":[],"review_version":1}