24 citations · 87 across the 27 of their papers we have counts for
32 papers
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…
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…
Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits
Qiwei Di, Tao Jin, Yue Wu +3
Dueling bandits is a prominent framework for decision-making involving preferential feedback, a valuable feature that fits various applications involving human interaction, such as…
Borda Regret Minimization for Generalized Linear Dueling Bandits
Yue Wu, Tao Jin, Hao Lou +2
Dueling bandits are widely used to model preferential feedback prevalent in many applications such as recommendation systems and ranking. In this paper, we study the Borda regret m…
Non-binary Codes for Correcting a Burst of at Most t Deletions
Shuche Wang, Yuanyuan Tang, Jin Sima +2
The problem of correcting deletions has received significant attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of…
Low-redundancy codes for correcting multiple short-duplication and edit errors
Yuanyuan Tang, Shuche Wang, Hao Lou +2
Due to its higher data density, longevity, energy efficiency, and ease of generating copies, DNA is considered a promising storage technology for satisfying future needs. However,…
Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons
Yue Wu, Tao Jin, Hao Lou +3
In heterogeneous rank aggregation problems, users often exhibit various accuracy levels when comparing pairs of items. Thus a uniform querying strategy over users may not be optima…
Data Deduplication with Random Substitutions
Hao Lou, Farzad Farnoud
Data deduplication saves storage space by identifying and removing repeats in the data stream. Compared with traditional compression methods, data deduplication schemes are more ti…
Error-correcting Codes for Short Tandem Duplication and Substitution Errors
Yuanyuan Tang, Farzad Farnoud
Due to its high data density and longevity, DNA is considered a promising medium for satisfying ever-increasing data storage needs. However, the diversity of errors that occur in D…
Error-correcting Codes for Noisy Duplication Channels
Yuanyuan Tang, Farzad Farnoud
Because of its high data density and longevity, DNA is emerging as a promising candidate for satisfying increasing data storage needs. Compared to conventional storage media, howev…
Coding for Optimized Writing Rate in DNA Storage
Siddharth Jain, Farzad Farnoud, Moshe Schwartz +1
A method for encoding information in DNA sequences is described. The method is based on the precision-resolution framework, and is aimed to work in conjunction with a recently sugg…
Rank Aggregation via Heterogeneous Thurstone Preference Models
Tao Jin, Pan Xu, Quanquan Gu +1
We propose the Heterogeneous Thurstone Model (HTM) for aggregating ranked data, which can take the accuracy levels of different users into account. By allowing different noise dist…
Single-Error Detection and Correction for Duplication and Substitution Channels
Yuanyuan Tang, Yonatan Yehezkeally, Moshe Schwartz +1
Motivated by mutation processes occurring in in-vivo DNA-storage applications, a channel that mutates stored strings by duplicating substrings as well as substituting symbols is st…
Evolution of -mer Frequencies and Entropy in Duplication and Substitution Mutation Systems
Hao Lou, Farzad Farnoud, Moshe Schwartz +1
Genomic evolution can be viewed as string-editing processes driven by mutations. An understanding of the statistical properties resulting from these mutation processes is of value…
Reconciling Similar Sets of Data
Ryan Gabrys, Farzad Farnoud
In this work, we consider the problem of synchronizing two sets of data where the size of the symmetric difference between the sets is small and, in addition, the elements in the s…
The Capacity of Some Pólya String Models
Ohad Elishco, Farzad Farnoud, Moshe Schwartz +1
We study random string-duplication systems, which we call Pólya string models. These are motivated by DNA storage in living organisms, and certain random mutation processes that af…
Duplication Distance to the Root for Binary Sequences
Noga Alon, Jehoshua Bruck, Farzad Farnoud +1
We study the tandem duplication distance between binary sequences and their roots. In other words, the quantity of interest is the number of tandem duplication operations of the fo…
Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms
Siddharth Jain, Farzad Farnoud, Moshe Schwartz +1
The ability to store data in the DNA of a living organism has applications in a variety of areas including synthetic biology and watermarking of patented genetically-modified organ…
The Capacity of String-Replication Systems
Farzad Farnoud, Moshe Schwartz, Jehoshua Bruck
It is known that the majority of the human genome consists of repeated sequences. Furthermore, it is believed that a significant part of the rest of the genome also originated from…
Rate-Distortion for Ranking with Incomplete Information
Farzad Farnoud, Moshe Schwartz, Jehoshua Bruck
We study the rate-distortion relationship in the set of permutations endowed with the Kendall Tau metric and the Chebyshev metric. Our study is motivated by the application of perm…
Multipermutation Codes in the Ulam Metric for Nonvolatile Memories
Farzad Farnoud, Olgica Milenkovic
We address the problem of multipermutation code design in the Ulam metric for novel storage applications. Multipermutation codes are suitable for flash memory where cell charges ma…
MetaPar: Metagenomic Sequence Assembly via Iterative Reclassification
Minji Kim, Jonathan G. Ligo, Amin Emad +3
We introduce a parallel algorithmic architecture for metagenomic sequence assembly, termed MetaPar, which allows for significant reductions in assembly time and consequently enable…