10 papers
The Minimum Number of Samples in the Labeled Coupon Collector Problem
Andrew Tan, Daniella Bar-Lev, Ryan Gabrys +2
The Labeled Coupon Collector Problem (LCCP) is an extension of the classical Coupon Collector Problem (CCP) in which one must deduce an unknown mapping between coupons and labels b…
More on Codes for Combinatorial Composite DNA
Zuo Ye, Omer Sabary, Ryan Gabrys +2
In this paper, we focus on constructions of unique-decodable/list-decodable on the recently studied -composite-asymmetric error-correcting codes (-CAECCs). Let be…
Error characterization and error correction approaches in combinatorial DNA-based storage
Inbal Preuss, Omer Sabary, Ryan Gabrys +3
Data storage in DNA has recently emerged as a promising archival solution, offering space-efficient and long-lasting digital storage. Combinatorial DNA encoding enhances this poten…
An Additive Approximation Scheme for Generating Dyadic Codings for the Outputs of an LLM
Daniella Bar-Lev, Farzad Farnoud, Ryan Gabrys
We study the problem of approximating a discrete probability distribution, such as the next-token distribution of a large language model, by a dyadic distribution induced by a bina…
Efficient Synthesis for Two-Dimensional Strand Arrays with Row Constraints
Boaz Moav, Ryan Gabrys, Eitan Yaakobi
In large-scale array-based DNA synthesis, optical and chemical coupling between nearby sites can limit simultaneous activations. Motivated by this constraint, we study strands synt…
Constructing Low-Redundancy Codes via Distributed Graph Coloring
Yuting Li, Ryan Gabrys, Farzad Farnoud
We present a general framework for constructing error-correcting codes using distributed graph coloring under the LOCAL model. Building on the correspondence between independent se…
Asymptotically Optimal Codes Correcting One Substring Edit
Yuting Li, Yuanyuan Tang, Hao Lou +2
The substring edit error is the operation of replacing a substring of with another string , where the lengths of and are bounded by a given constant . It enco…
Linear List Decodable Edit-Correcting Codes with Rate Approaching
Yuting Li, Ryan Gabrys, Farzad Farnoud
Linear codes correcting one deletions have rate at most . In this paper, we construct linear list decodable codes correcting edits with rate approaching and reasonable lis…
Making it to First: The Random Access Problem in DNA Storage
Avital Boruchovsky, Ohad Elishco, Ryan Gabrys +3
In this paper, we study the Random Access Problem in DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. In this…
Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars
Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami
We modify Cheraghchi-Nakos [CN20] and Price-Scarlett's [PS20] fast binary splitting approach to nonadaptive group testing. We show that, to identify a uniformly random subset of $k…