10 papers
Capacity of Additive-Noise Sticky Channels
Cécile Bouette, Samuel Pearson, Roni Con +1
Sticky channels, which never destroy nor create runs, are some of the simplest types of channels with synchronization errors (such as deletions, insertions, and replications). Desp…
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 show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one…
The Synthesis-Sequencing Channel for DNA-based Data Storage
Keshav Goyal, Samuel Pearson, João Ribeiro +1
We introduce and study the synthesis-sequencing channel, a two-stage model for DNA-based data storage that jointly captures synthesis and sequencing effects. The synthesis-sequenci…
Improved Capacity Upper Bounds for the Deletion Channel using a Parallelized Blahut-Arimoto Algorithm
Martim Pinto, João Ribeiro
We present an optimized implementation of the Blahut-Arimoto algorithm via GPU parallelization, which we use to obtain improved upper bounds on the capacity of the binary deletion…
Correcting Contextual Deletions in DNA Nanopore Readouts
Yuan-Pon Chen, Olgica Milenkovic, João Ribeiro +1
The problem of designing codes for deletion-correction and synchronization has received renewed interest due to applications in DNA-based data storage systems that use nanopore seq…
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…
Channels with Input-Correlated Synchronization Errors
Roni Con, João Ribeiro
"Independent and identically distributed" errors do not accurately capture the noisy behavior of real-world data storage and information transmission technologies. Motivated by thi…
Nearly-Linear Time Seeded Extractors with Short Seeds
Dean Doron, João Ribeiro
Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameter…
Low-Degree Polynomials Are Good Extractors
Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff +1
We prove that random low-degree polynomials (over ) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomne…