6 papers · 1 filter
The Insertion List-Decoding Capacity and an Improved Bound on the Deletion List-Decoding Capacity
Roni Con, Dean Doron, João Ribeiro
Informally, the capacity of list-decoding in a given adversarial error model is the largest rate at which we can list-decode with list size polynomial in the block length. The capa…
Discrepancy for Random Linear Codes
Dean Doron, Tal Leonov, Jonathan Mosheiff +3
We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates…
Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound
Gil Cohen, Dean Doron, Noam Goldgraber +1
One of the oldest problems in coding theory is to match the Gilbert-Varshamov bound with explicit binary codes. Over larger-yet still constant-sized-fields, algebraic-geometry code…
List-Recovery of Random Linear Codes over Small Fields
Dean Doron, Jonathan Mosheiff, Nicolas Resch +1
We study list-recoverability of random linear codes over small fields, both from errors and from erasures. We consider codes of rate -close to capacity, and aim to bound the dep…
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
Dean Doron, Jonathan Mosheiff, Mary Wootters
The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate has relative distance at least $\fra…
Random Reed-Solomon Codes are List Recoverable with Optimal List Size
Dean Doron, S. Venkitesh
We prove that Reed-Solomon (RS) codes with random evaluation points are list recoverable up to capacity with optimal output list size, for any input list size. Namely, given an inp…