More Like this

1. On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction

   Cheng, Kuan; Grigorescu, Elena; Li, Xin; Sudan, Madhu; Zhu, Minshen (July 2024, IEEE Press)

   The goal of the trace reconstruction problem is to recover a string x E {0, 1} given many independent traces of x, where a trace is a subsequence obtained from deleting bits of x independently with some given probability. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the state-of-the-art result of Chase (STOC 2021), which is based on statistics of arbitrary length-k subsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences of contiguous k-bit strings (a.k.a, k-mers) in the initial string x, for k = Mazooji and Shomorony (ISIT 2023) show that such statistics (called k-mer density map) can be estimated within accuracy from poly(n, 2k, l/e) traces. We call an algorithm to be k-mer-based if it reconstructs x given estimates of the k-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any k-mer-based algorithm for trace reconstruction must use exp n)) traces, under the assumption that the estimator requires poly(2k, 1 e) traces, thus establishing the optimality of this number of traces. Our analysis also shows that the analysis technique used by Chase is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of n in the number of samples needed for an optimal algorithm, and show that this factor of n loss may be necessary under general “model estimation” settings. 

   more » « less
2. On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction

   Cheng, Kuan; Grigorescu, Elena; Li, Xin; Sudan, Madhu; Zhu, Minshen (July 2024, IEEE Press)

   The goal of the trace reconstruction problem is to recover a string x E {0, 1} given many independent traces of x, where a trace is a subsequence obtained from deleting bits of x independently with some given probability. In this paper we consider two kinds of algorithms for the trace reconstruction problem. We first observe that the state-of-the-art result of Chase (STOC 2021), which is based on statistics of arbitrary length-k subsequences, can also be obtained by considering the “k-mer statistics”, i.e., statistics regarding occurrences of contiguous k-bit strings (a.k.a, k-mers) in the initial string x, for k = Mazooji and Shomorony (ISIT 2023) show that such statistics (called k-mer density map) can be estimated within accuracy from poly(n, 2k, l/e) traces. We call an algorithm to be k-mer-based if it reconstructs x given estimates of the k-mer density map. Such algorithms essentially capture all the analyses in the worst-case and smoothed-complexity models of the trace reconstruction problem we know of so far. Our first, and technically more involved, result shows that any k-mer-based algorithm for trace reconstruction must use exp n)) traces, under the assumption that the estimator requires poly(2k, 1 e) traces, thus establishing the optimality of this number of traces. Our analysis also shows that the analysis technique used by Chase is essentially tight, and hence new techniques are needed in order to improve the worst-case upper bound. Our second, simple, result considers the performance of the Maximum Likelihood Estimator (MLE), which specifically picks the source string that has the maximum likelihood to generate the samples (traces). We show that the MLE algorithm uses a nearly optimal number of traces, i.e., up to a factor of n in the number of samples needed for an optimal algorithm, and show that this factor of n loss may be necessary under general “model estimation” settings. 

   more » « less
3. Polynomial-time Trace Reconstruction in the Smoothed Complexity Model

   https://doi.org/10.1145/3560819  

   Chen, Xi; De, Anindya; Lee, Chin Ho; Servedio, Rocco; Sinha, Sandip (July 2025, ACM Transactions on Algorithms)

   In thetrace reconstruction problem, an unknown source stringx∈ {0,1}ⁿis sent through a probabilisticdeletion channelthat independently deletes each bit with probability δ and concatenates the surviving bits, yielding atraceofx. The problem is to reconstructxgiven independent traces. This problem has received much attention in recent years both in the worst-case setting wherexmay be an arbitrary string in {0,1}ⁿ[7,8,10,11,12,23] and in the average-case setting wherexis drawn uniformly at random from {0,1}ⁿ[7,8,12,13,25]. This article studies trace reconstruction in thesmoothed analysissetting, in which a “worst-case” stringx^worstis chosen arbitrarily from {0,1}ⁿ, and then a perturbed versionxofx^worstis formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstructxgiven independent traces from it. Our main result is an algorithm that, for any constant perturbation rate 0< σ < 1 and any constant deletion rate 0 < δ < 1, uses poly(n) running time and traces and succeeds with high probability in reconstructing the stringx. This stands in contrast with the worst-case version of the problem, for which\(\text{exp}(\tilde{O}(n^{1/5}))\)is the best known time and sample complexity [8]. Our approach is based on reconstructingxfrom the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly(n)-time procedure for reconstructing the multiset of allO(logn)-length subwords of any source stringx∈ {0,1}ⁿgiven access to traces ofx. 

   more » « less
4. New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling

   Compton, Spencer; Mitrovic, Slobodan; Rubinfeld, Ronitt (July 2023, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023)

   Interval scheduling is a basic problem in the theory of algorithms and a classical task in combinatorial optimization. We develop a set of techniques for partitioning and grouping jobs based on their starting and ending times, that enable us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in dynamic and local settings of computation leads to several new results. For (1+ε)-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O((log n)/ε) update and O(log n) query worst-case time. Further, we design a local computation algorithm that uses only O((log N)/ε) queries when all jobs are length at least 1 and have starting/ending times within [0,N]. Our techniques are also applicable in a setting where jobs have rewards/weights. For this case we design a fully dynamic deterministic algorithm whose worst-case update and query time are poly(log n,1/ε). Equivalently, this is the first algorithm that maintains a (1+ε)-approximation of the maximum independent set of a collection of weighted intervals in poly(log n,1/ε) time updates/queries. This is an exponential improvement in 1/ε over the running time of a randomized algorithm of Henzinger, Neumann, and Wiese [SoCG, 2020], while also removing all dependence on the values of the jobs' starting/ending times and rewards, as well as removing the need for any randomness. We also extend our approaches for interval scheduling on a single machine to examine the setting with M machines. 

   more » « less
5. New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling

   Compton, S.; Mitrovic, S.; Rubinfeld, R. (January 2023, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023))

   Interval scheduling is a basic problem in the theory of algorithms and a classical task in combinatorial optimization. We develop a set of techniques for partitioning and grouping jobs based on their starting and ending times, that enable us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in dynamic and local settings of computation leads to several new results. For (1+ε)-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O((log n)/ε) update and O(log n) query worst-case time. Further, we design a local computation algorithm that uses only O((log N)/ε) queries when all jobs are length at least 1 and have starting/ending times within [0,N]. Our techniques are also applicable in a setting where jobs have rewards/weights. For this case we design a fully dynamic deterministic algorithm whose worst-case update and query time are poly(log n,1/ε). Equivalently, this is the first algorithm that maintains a (1+ε)-approximation of the maximum independent set of a collection of weighted intervals in poly(log n,1/ε) time updates/queries. This is an exponential improvement in 1/ε over the running time of a randomized algorithm of Henzinger, Neumann, and Wiese [SoCG, 2020], while also removing all dependence on the values of the jobs' starting/ending times and rewards, as well as removing the need for any randomness. We also extend our approaches for interval scheduling on a single machine to examine the setting with M machines. 

   more » « less