Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes

Jonathan Mosheiff; Sergey Komech

REVIEW 2 major objections 4 minor 10 references

Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes

T0 review · 2 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Alphabet-permutation codes match plain random codes' list-recovery guarantees.

desk verdict 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. read the letter →

arxiv 2502.05858 v2 pith:45462T4N submitted 2025-02-09 cs.IT math.IT

Sergey Komech , Jonathan Mosheiff This is my paper · ORCID

classification cs.ITmath.IT MSC 94B6594B35

keywords alphabet-permutationcodeslist-recoverabilitylist-decodingEliasboundrandomness-efficientm-wiseindependentpermutationsnon-additivederandomization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What'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.

Soft 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.

Bottom 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.

Referee Report

2 major / 4 minor

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.

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 (2)

[§2.5 (Proposition 2.6), §2.7 (Theorem 1.1)] 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.
[§3, Eq. (4)] 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.

minor comments (4)

[§2.5, §3] 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.
[§2.6, Lemma 2.12] 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.
[§2.7, Theorem 2.18] 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.
[§3, Claim 3.4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the list-recoverability guarantee is derived from first principles via a potential-function argument; cited external tools are used as black boxes, and the paper's self-citations are contextual only.

full rationale

The paper's central derivation is self-contained rather than circular. Proposition 2.6 is proved by a potential-function argument (Section 3) that starts from the definition of the B-mixing distribution and bounds E[K_i | C_{i-1}] <= K_{i-1}^2 via Markov's inequality; there is no fitted parameter that is later reported as a prediction. Corollary 2.7 instantiates Proposition 2.6 with B = B_{rho,ell} using standard estimates on |B| from [Res20], and Theorem 2.13 follows from Lemma 2.12, which shows that ell-wise independent permutations are B_{rho,ell}-mixing. Theorem 1.1 then combines the external results [KNR09] (small delta-independent permutation families) and [AL13] (conversion of near-independence to true independence in total variation); both are cited as independent tools, not as author-derived premises. The rate formula 1 - h* - (log_q binom(q, ell)+1)/(n(L+1)) - eta is derived from the counting of bad sets and the potential threshold q, not assumed from the conclusion. The self-citations [LMS24] and [MRSY24] appear only in the introduction as contextual discussion of lower bounds and the Elias bound; they are not used in the proof of the main theorem. The proof gap noted for Eq. (4) regarding the eta lower bound when k > n is a correctness concern, not a circularity concern. Overall, the derivation does not reduce to its own inputs.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No fitted constants, no new physical entities. The only new object is the AP code family itself, which is a construction rather than a postulated entity needing external evidence.

free parameters (2)

η = η ≥ 2 log_q(2n/ln2)/n; later set to 2 log_q(nk)/n
Slack parameter in rate and failure exponent; chosen small so λ_k ≤ 2 q^{-ηn}. Not fitted to data.
δ = 1/(c n^2 k q^{4ℓ})
TV error of the approximate ℓ-wise independent family; chosen to make the second error term O(1/n). Not fitted to data.

assumptions (4)

standard math There exist ℓ-wise δ-independent permutation families of size exp(O(ℓ log q + log 1/δ)) with efficient evaluation ([KNR09, Thm 5.9]).
Used in Theorem 1.1 to sample Π entries with few random bits (Section 2.7).
standard math Any m-wise δ-independent distribution over S_Σ is O(δ q^{4m})-close in TV to a truly m-wise independent distribution ([AL13, Thm 2.18]).
Used to transfer list-recovery from idealized ℓ-wise independent ensemble to the small-family ensemble (Section 2.7).
standard math Bad sets in B_{ρ,ℓ} have size at most q^{n h*_{q,ℓ}(ρ)} and the number of such sets is at most binom(q,ℓ)^n ([Res20, Prop 2.4.11]).
Used in Corollary 2.7 to set β = h* and bound |B|.
domain assumption B_{ρ,ℓ} is regular: closed under a transitive action of coordinate-wise permutations.
Needed for orbit-counting in Claim 3.3; true for the product action of S_Σ on Σ^n.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes." pith.science (2026). https://pith.science/paper/45462T4N

@misc{pith2026250205858,
  author       = {Pith},
  title        = {Pith review of: Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/45462T4N}},
  note         = {Machine review of arXiv:2502.05858}
}

read the original abstract

We introduce alphabet-permutation (AP) codes, a new family of error-correcting codes defined by iteratively applying random coordinate-wise permutations to a fixed initial word. A special case recovers random additive codes and random binary linear codes, where each permutation corresponds to an additive shift over a finite field. We show that when these permutations are drawn from a suitably ``mixing'' distribution, the resulting code is almost surely list-recoverable with list size proportional to the inverse of the gap to capacity. Compared to any linear code, our construction achieves exponentially smaller list sizes at the same rate. Previously, only fully random codes were known to attain such parameters, requiring exponentially many random bits and offering no structure. In contrast, AP codes are structured and require only polynomially many random bits -- providing the first such construction to match the list-recovery guarantees of random codes.

Figures

Figures reproduced from arXiv: 2502.05858 by the authors.

**Figure 1.** Computing EncΠ(z) for n = 6, k = 3 and z = (1, 0, 1). Iterative Generation. The encoding process can also be viewed as building up CΠ in stages: starting from the all-zero vector, we repeatedly apply coordinate-wise permutations based on each row of Π. Formally, define a sequence of multisets C0, . . . , Ck ⊆ Σ n by: C0 := {(0, . . . , 0)} and Ci := Ci−1 ∪ (Πi,1(x1), . . . , Πi,n(xn)) | x ∈ Ci−1 [PITH_FULL_IMAGE:… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages

[1]

Almost K-Wise vs. k-Wi se Independent Permuta- tions, and Uniformity for General Group Actions

[AL13] Noga Alon and Shachar Lovett. “Almost K-Wise vs. k-Wi se Independent Permuta- tions, and Uniformity for General Group Actions”. In: Theory of Computing 9.15 (May 30, 2013), pp. 559–577. [CZ24] Yeyuan Chen and Zihan Zhang. Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds

work page 2013
[9]

Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes

arXiv: 2402.11533 [cs.IT]. [NPR11] Hung Q. Ngo, Ely Porat, and Atri Rudra. “Eﬃciently De codable Error-Correcting List Disjunct Matrices and Applications”. In:International Colloquium on Automata, Languages, and Programming. Springer, 2011, pp. 557–568. [Res20] Nicolas Resch. “List-Decodable Codes: (Randomize d) Constructions and Applica- tions”. Pittsbur...

work page Pith review arXiv 2011
[10]

Tighter List-Size Bounds for List-Decoding and Recovery of Folded Reed-Solomon and Multiplicity Codes

48550/ARXIV.2312.17097. arXiv: 2312.17097. [TZ04] A. Ta-Shma and D. Zuckerman. “Extractor Codes”. In: IEEE Trans. Inf. Theor. 50.12 (Dec. 1, 2004), pp. 3015–3025. issn: 0018-9448. 17

work page Pith review arXiv 2004
[229]

Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Z entrum f¨ ur Informatik, 2022, 55:1–55:17

Leibniz International Procee dings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Z entrum f¨ ur Informatik, 2022, 55:1–55:17. isbn: 978-3-95977-235-8. [Eli57] Peter Elias. List Decoding for Noisy Channels . Technical Report

work page 2022
[234]

ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk

LIPIcs. 2022, 7:1–7:17. [GNPRS13] Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra , and Martin J. Strauss. “ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk”. In: Proceedings of the 40th In- ternational Conference on Automata, Languages, and Program ming - Volume Part I. 2013, pp. 461–472. isbn: 978-3-642-39205-4. [GR08] Venkatesan Guruswami and Atri Rudra...

work page 2008
[315]

doi: 10.1007/978-3-031-58737-5_11

isbn: 978-3-031- 58737-5. doi: 10.1007/978-3-031-58737-5_11 . [MRSY24] Jonathan Mosheiﬀ, Nicolas Resch, Kuo Shang, and Che n Yuan.Randomness-Eﬃcient Constructions of Capacity-Achieving List-Decodable Codes

work page doi:10.1007/978-3-031-58737-5_11
[1957]

On the List-Decodability of Random Linear Codes

[GHK11] Venkatesan Guruswami, Johan H˚ astad, and Swastik K opparty. “On the List-Decodability of Random Linear Codes”. In: IEEE Trans. Inf. Theory 57.2 (2011), pp. 718–725. [GHSZ02] Venkatesan Guruswami, Johan H˚ astad, Madhu Sudan , and David Zuckerman. “Com- binatorial Bounds for List Decoding”. In: IEEE Trans. Inf. Theory 48.5 (2002), pp. 1021–1034. [...

work page 2011
[2024]

High-Probability Lis t-Recovery, and Applica- tions to Heavy Hitters

arXiv: 2408.15925 [cs.IT] . [DW22] Dean Doron and Mary Wootters. “High-Probability Lis t-Recovery, and Applica- tions to Heavy Hitters”. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP

arXiv

Show all 10 references

[2025]

Improved List-Decodabili ty of Random Linear Binary Codes

arXiv: 2502.13877 [cs] . url: http://arxiv.org/abs/2502.13877 (visited on 04/23/2025). Pre-published. [LW21] Ray Li and Mary Wootters. “Improved List-Decodabili ty of Random Linear Binary Codes”. In: IEEE Trans. Inf. Theory 67.3 (2021), pp. 1522–1536. 16 [MNPY24] Hemanta K. Ma...

2021 arXiv
[3268]

Local List Recovery of High- Rate Tensor Codes and Applications

[HRW20] Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. “ Local List Recovery of High- Rate Tensor Codes and Applications”. In: SIAM Journal on Computing 49.4 (Jan. 2020), FOCS17–157. issn: 0097-5397. [HW18] Brett Hemenway and Mary Wootters. “Linear-Time List Recovery of Hig...

2024

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Almost K-Wise vs. k-Wi se Independent Permuta- tions, and Uniformity for General Group Actions

[AL13] Noga Alon and Shachar Lovett. “Almost K-Wise vs. k-Wi se Independent Permuta- tions, and Uniformity for General Group Actions”. In: Theory of Computing 9.15 (May 30, 2013), pp. 559–577. [CZ24] Yeyuan Chen and Zihan Zhang. Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds

work page 2013

[2] [9]

Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes

arXiv: 2402.11533 [cs.IT]. [NPR11] Hung Q. Ngo, Ely Porat, and Atri Rudra. “Eﬃciently De codable Error-Correcting List Disjunct Matrices and Applications”. In:International Colloquium on Automata, Languages, and Programming. Springer, 2011, pp. 557–568. [Res20] Nicolas Resch. “List-Decodable Codes: (Randomize d) Constructions and Applica- tions”. Pittsbur...

work page Pith review arXiv 2011

[3] [10]

Tighter List-Size Bounds for List-Decoding and Recovery of Folded Reed-Solomon and Multiplicity Codes

48550/ARXIV.2312.17097. arXiv: 2312.17097. [TZ04] A. Ta-Shma and D. Zuckerman. “Extractor Codes”. In: IEEE Trans. Inf. Theor. 50.12 (Dec. 1, 2004), pp. 3015–3025. issn: 0018-9448. 17

work page Pith review arXiv 2004

[4] [229]

Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Z entrum f¨ ur Informatik, 2022, 55:1–55:17

Leibniz International Procee dings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Z entrum f¨ ur Informatik, 2022, 55:1–55:17. isbn: 978-3-95977-235-8. [Eli57] Peter Elias. List Decoding for Noisy Channels . Technical Report

work page 2022

[5] [234]

ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk

LIPIcs. 2022, 7:1–7:17. [GNPRS13] Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra , and Martin J. Strauss. “ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk”. In: Proceedings of the 40th In- ternational Conference on Automata, Languages, and Program ming - Volume Part I. 2013, pp. 461–472. isbn: 978-3-642-39205-4. [GR08] Venkatesan Guruswami and Atri Rudra...

work page 2008

[6] [315]

doi: 10.1007/978-3-031-58737-5_11

isbn: 978-3-031- 58737-5. doi: 10.1007/978-3-031-58737-5_11 . [MRSY24] Jonathan Mosheiﬀ, Nicolas Resch, Kuo Shang, and Che n Yuan.Randomness-Eﬃcient Constructions of Capacity-Achieving List-Decodable Codes

work page doi:10.1007/978-3-031-58737-5_11

[7] [1957]

On the List-Decodability of Random Linear Codes

[GHK11] Venkatesan Guruswami, Johan H˚ astad, and Swastik K opparty. “On the List-Decodability of Random Linear Codes”. In: IEEE Trans. Inf. Theory 57.2 (2011), pp. 718–725. [GHSZ02] Venkatesan Guruswami, Johan H˚ astad, Madhu Sudan , and David Zuckerman. “Com- binatorial Bounds for List Decoding”. In: IEEE Trans. Inf. Theory 48.5 (2002), pp. 1021–1034. [...

work page 2011

[8] [2024]

High-Probability Lis t-Recovery, and Applica- tions to Heavy Hitters

arXiv: 2408.15925 [cs.IT] . [DW22] Dean Doron and Mary Wootters. “High-Probability Lis t-Recovery, and Applica- tions to Heavy Hitters”. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP

arXiv