title: Polynomial-time trace reconstruction in the smoothed complexity model
authors: Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha
text: 
  
  
  
  
  
  Polynomial-time trace reconstruction
   
  in the smoothed complexity model
  
      
  Xi ChenSupported by NSF grants CCF-1703925 and IIS-1838154. 
  
  
  Columbia University
  
  xichen@cs.columbia.edu
  Anindya DeSupported by NSF grants CCF-1926872 and CCF-1910534.
  
  
  University of Pennsylvania
  
  anindyad@cis.upenn.edu
  Chin Ho LeeSupported by a grant from the Croucher Foundation and by the Simons Collaboration on Algorithms and Geometry.
  
  
  Columbia University
  
  c.h.lee@columbia.edu
  Rocco A. ServedioSupported by NSF grants CCF-1814873, IIS-1838154, CCF-1563155, and by the Simons Collaboration on Algorithms and Geometry. 
  
  
  Columbia University
  
  rocco@cs.columbia.edu
  Sandip SinhaSupported by NSF grants  CCF-1714818, CCF-1822809, IIS-1838154, CCF-1617955, CCF-1740833, and by the Simons Collaboration on Algorithms and Geometry.
  
  
  Columbia University
  
  sandip@cs.columbia.edu
  
      December 30, 2023
  ===================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  
  empty
  
  
  
  
  In the trace reconstruction problem, an unknown source string x ∈{0,1}^n is sent through a probabilistic deletion channel which independently deletes each bit with probability δ and concatenates the surviving bits, yielding a trace of x. The problem is to reconstruct x given independent traces. This problem has received much attention in recent years both in the worst-case setting  where x may be an arbitrary string in {0,1}^n <cit.> and in the average-case setting where x is drawn uniformly at random from {0,1}^n <cit.>.
  
  This paper studies trace reconstruction in the smoothed analysis setting, in which  a “worst-case” string x^ is chosen arbitrarily from {0,1}^n, and then a  perturbed version  of x^ is formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstruct  given independent traces from it.
  
  Our main result is an algorithm which, for any constant perturbation rate 0<σ < 1 and any constant deletion rate 0 < δ < 1, uses (n) running time and traces and succeeds with high probability in reconstructing the string . This stands in contrast with the worst-case version of the problem, for which exp(O(n^1/3)) is the best known time and sample complexity <cit.>.
  
  Our approach is based on reconstructing  from 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 (n)-time procedure for reconstructing the multiset of all O(log n)-length subwords of any source string x∈{0,1}^n given access to traces of x.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § INTRODUCTION
   
  
  Trace reconstruction is a simple-to-state algorithmic problem which has been intensively studied yet remains mysterious in many respects.  The problem 
    captures some of the core algorithmic challenges that arise in dealing with the deletion channel; this is a noise process which, when given an input string, independently deletes each coordinate with some fixed probability δ and outputs the concatenation of surviving coordinates.  In the trace reconstruction problem an algorithm is given access to independent traces of a fixed unknown string x ∈^n, where a “trace” of x, denoted ∼_δ(x), is the string  that results from passing x through a deletion channel. The task is to use these traces to reconstruct the unknown string x. 
  
  Variants of the trace reconstruction problem have a long history, going back at least to <cit.>.  The problem was studied on and off throughout the 2000s <cit.>, and has seen a renewed surge of recent interest over the past few years <cit.>Did I miss any relevant references here? Should we take out our two population recovery papers and the Narayanan paper or leave them in? Sandip: I am in favour of keeping the pop rec papers in, and maybe add `... versions of the problem (and some generalizations of it).' at the end of the sentence. Different note about references:  visiting https://arxiv.org/abs/1801.04783https://arxiv.org/abs/1801.04783, it looks like in late April 2020 a new version of this was uploaded with Alex Zhai added as an author. I added this as a separate citation since just replacing <cit.> with it would give an inaccurate chronology. with the development of new algorithms and lower bounds for both the worst-case and average-case versions of the problem as well as various generalizations. Below we describe these two versions of the problem and recall the current state of the art for each of them.
  
  
  
   §.§ Prior work:  Worst-case and average-case trace reconstruction
  
  
  The original version of the trace reconstruction problem is the worst-case version, in which the unknown string x is an arbitrary (i.e. adversarially chosen) string from ^n. This version of the problem has proved to be quite challenging; the first non-trivial result is due to Batu et al. <cit.>, who gave a (n)-time algorithm that uses (n) traces and succeeds when the deletion rate δ is very small, at most n^-1/2 - for any > 0.  In <cit.> Holenstein et al. gave an algorithm that runs in exp(Õ(n^1/2)) time using exp(Õ(n^1/2)) traces and succeeds for any δ bounded away from 1 by a constant. Simultaneous and independent works of De et al. <cit.> and Nazarov and Peres <cit.> gave an algorithm that improves the running time and sample complexity of <cit.> to exp(O(n^1/3)). In this same constant-δ regime, successively stronger lower bounds on the required sample complexity were given by <cit.>, culminating in a Ω̃(n^3/2) lower bound due to Chase <cit.>.
  
  Another natural variant of the trace reconstruction problem is the average-case version; in this variant the unknown string x is assumed to be drawn uniformly at random from ^n, and the goal is for the algorithm to succeed with high probability over the random choice of x.  This problem variant is motivated both by the apparent difficulty of the worst-case problem and by the fact that in various application domains it may be overly pessimistic to assume that the input string x is adversarially generated.  Much more efficient algorithms are known for the average-case problem: several  early works <cit.> gave efficient algorithms that succeed for trace reconstruction of almost all x ∈^n for various o_n(1) deletion rates δ, and <cit.> gave an 
    algorithm that runs in (n) time using (n) traces when δ is at most some sufficiently small constant.  More recent results of  Peres and Zhai <cit.> and Holden et al. <cit.>, which build on worst-case trace reconstruction results of <cit.>, substantially improve on this, with <cit.> giving an algorithm which uses exp(O(log^1/3 n )) traces to reconstruct a random x∈{0,1}^n in n^1+o_n(1) time when  the deletion rate is any constant bounded away from 1.
  
  Summarizing the results described above, the current exp(O(n^1/3))  state-of-the-art for worst-case trace reconstruction is exponentially higher than the current exp(O( log^1/3 n )) state-of-the-art for average-case trace reconstruction.  Given this substantial gap, it is natural to investigate intermediate formulations of the problem between the worst-case and average-case models.   
  
  
  
  
   §.§ This work:  Smoothed analysis of trace reconstruction
  
  
  The well-studied  smoothed analysis model, introduced by Spielman and Teng <cit.>, provides a natural framework for interpolating between worst-case and average-case complexity. In smoothed analysis the input to an algorithm is obtained by applying a random σ-perturbation to a worst-case input instance; here σ is a “perturbation rate,”  which it is natural to scale so that σ=1 corresponds to a truly random instance and σ=0 corresponds to a worst-case instance.  By choosing intermediate settings of σ it is possible to interpolate between worst-case and average-case problem variants.
  
  We now give a detailed statement of the smoothed trace reconstruction problem that we consider.   First, a “worst-case” string x^ is chosen arbitrarily from ^n, and then a randomly perturbed version  of the string x^ is formed by independently replacing each coordinate of x^ by a uniform random bit with probability σ.Removed the `> 0' restriction on σ for the definition of the model. The very next sentence considers what happens when σ=0.  
  The goal is to reconstruct  given access to independent traces drawn from _δ(). Note that when σ=0 this reduces to the worst-case trace reconstruction problem, and when σ=1 this reduces to the average-case problem.
  
  As our main result, we give an algorithm for the smoothed trace reconstruction problem. For any initial string x^, our algorithm can recover a 1-1/(n) fraction of perturbed strings  obtained from x^ (for any (n)) 
  in polynomial time for any constant perturbation rate 0 < σ≤ 1 and any constant deletion rate 0 < δ < 1. 
  
  More precisely, the main theorem we prove is the following:
  
   
  Let 0 < δ, η, τ <1 and 0 < σ≤ 1. 
  Let x^ be an arbitrary and unknown string in ^n and let  be formed from x^ by independently replacing each bit of x^ with a uniform random bit from  with probability σ. 
  
  There is an algorithm with the following guarantee: with probability at least 1-η (over the random generation of  from x^), it is the case that
  the algorithm, given access to independent traces drawn from _δ(), outputs the string  with
  probability at least 1-τ (over the random traces drawn from _δ()). Its running time, as well as the number of traces it uses, is
  
      (n/η)^O(1/σ(1-δ)log2/1-δ)log1/τ.
  
  
  
  
  
  
   
  Let 0 < σ,δ <1.
  Let x^ be an arbitrary and unknown string in ^n and let  be formed from x^ by independently replacing each bit of x^ with a uniform random bit from  with probability σ. 
  
  There is an algorithm which, given access to independent traces drawn from _δ(), with probability at least 1 - τ (over the random generation  of  from x^ and random traces drawn from _δ()) outputs the string . The running time of the algorithm is The following is what we get just by blindly combining <Ref> and <Ref>, but this doesn't seem like the best thing to do because of the τ appearing in the exponent.  Shouldn't we instead consider the basic algorithm as running with τ = 0.01, say, and then think about running it log(1/τ) times and taking majority vote. This would get rid of the τ in the exponents, and would actually get rid of the τ's almost everywhere in the whole paper except in the statement of <Ref>, which seems like a good thing.  
  
  If you agree, let's do this?
   
  
      (n) · (1-δ)^-O(log(n/τ))/σ(1-δ)·log (1/τ).
  
  and the number of traces it uses is
  
      (1-δ)^-O(log(n/τ))/σ(1-δ)log (4kn/τ).
  
  
  
  
  It is interesting that while the best currently known algorithms for the worst-case problem, corresponding to σ=0, require exp(O(n^1/3)) time, for any constant perturbation rate we can solve the problem in a dramatically more efficient way. Intuitively, this shows that worst-case instances for trace reconstruction are “few and far between,” in the sense that even a small perturbation of such an instance typically makes it much easier to solve.
  
  
  
  
  
  
   §.§ Techniques
  
  
  Before describing our approach we briefly recall some of the methods used in prior work for the worst-case and average-case problems and discuss why these approaches do not seem applicable to the smoothed problem that we consider.
  
  Worst-case algorithms.
  All of the known worst-case algorithms <cit.> for deletion rates bounded away from 1 are “mean-based,” meaning that they only use (estimates of) the n expected values _∼_δ(x)[_i], i=1,…,n. The two papers <cit.> both show that mean-based algorithms can only succeed if they are given estimates of these expectations that are additively ±exp(-Ω(n^1/3))-accurate, and hence mean-based algorithms must inherently use exp(Ω(n^1/3)) traces for the worst-case problem.  Inspection of  <cit.> shows that these worst-case lower bounds  
  
    for mean-based algorithms 
  in fact hold for a 1 - o_n(1) fraction of strings in ^n. Thus, the mean-based algorithmic approach of <cit.> will not work for our smoothed variant of the problem (and indeed our algorithm is not a mean-based algorithm).
  
  
  Average-case algorithms.
  The average-case algorithms of <cit.> work by aligning individual traces (and are not mean-based).  The analysis builds off of some of the structural results established in <cit.>, but also employs sophisticated probabilistic arguments which heavily depend on the randomness of the source string x being reconstructed.  
  
  As noted in <cit.>, their average-case algorithm extends to the setting in which the target string x is drawn from the p-biased distribution over ^n (under which each bit x_i is independently taken to be 1 with probability p).  Taking p=σ/2, this corresponds to our smoothed analysis model in the special case in which the original  string x^ is promised to be the string 0^n.  Equivalently, we can view our smoothed analysis problem as a more challenging variant of p-biased average-case trace reconstruction — more challenging because the initial string (x^) is no longer promised to be 0^n, but rather itremove the `it'?is both arbitrary and moreover unknown to the reconstruction algorithm. It is not  clear how to extend the p-biased average-case results of <cit.> even to the setting in which the starting string x^  is a known arbitrary string, let alone to our setting in which x^ is both arbitrary and unknown.
  
  
  
  
  
   §.§ Our approach: Reconstruction from subwords and the subword deck
   reconstruction problem
  
  
  In contrast with prior algorithms for the worst-case and average-case problem, our approach is based on first reconstructing subwords of the target string and then reconstructing the target string from those subwords.  Recall that a subword of a string x=(x_1,…,x_n) is a sequence of contiguous characters of x, i.e. a (b-a+1)-character string (x_a,x_a+1,…,x_b)  for some 1 ≤ a ≤ b ≤ n.
  
  
  
  Reconstruction from subwords.
  Given a length 1 ≤ k ≤ n, let us write (x,k) to denote the multiset of all n-k+1 length-k subwords of x; we refer to this multiset as the k-subword deck of x. For example, if n=7 and k=3, then the k-subword deck of x=1101011 would be the 5-element multiset {010, 011, 101, 101, 110}. 
  
  In general the k-subword deck of x may not uniquely identify the string x within ^n unless k is very large; for example, the two multisets 
  
      (0^n/41^n/4 - 1 0^n/4 1^n/4+ 1,k)   and  (0^n/41^n/4+10^n/41^n/4 - 1,k)
  
  are identical for every k ≤ n/4-1. This simple example shows that for worst-case strings x,  the k-subword deck of x may not suffice to information-theoretically specify x unless k is linear in n.
  
  The starting point of our approach is the observation that the situation is markedly better for random perturbations of worst-case strings:  for any worst-case string x^∈^n, with high probability a random σ-perturbation  of x^ is such that (,k) does uniquely identify  within ^n even if k is relatively small. Moreover, there is an efficient algorithm to reconstruct  from (,k). This is captured by the following result, which we prove in <Ref>:
  
  
  
   
  Let 0 < σ,η
  < 1.  There is a deterministic algorithm Reconstruct-from-subword-deck which takes as input the k-subword deck (x,k) of a string x ∈^n, where k = O(log(n /η)/σ), and outputs either a string in ^n or “.” Reconstruct-from-subword-deck runs in (n) time and has the following property:  for any x^∈^n, if  is a random σ-perturbation of x^ (i.e.  is obtained by independently replacing each bit of x^ with a uniform random bit with probability σ), then with probability at least 1-η 
  the output of Reconstruct-from-subword-deck on input (,k) is the string .
  
  
  
  The subword deck reconstruction problem.  <Ref> naturally motivates the algorithmic problem of subword deck reconstruction:  given access to independent traces drawn from _δ(x) and a length k, can we reconstruct the k-subword deck of x?  Our main algorithmic contribution is an efficient algorithm for this problem:
  
   
  Let 0 < δ,τ < 1. There is an algorithm Reconstruct-subword-deck which takes as input a parameter 1 ≤ k ≤ n and access to independent traces of an unknown source string x ∈^n.
  The running time of Reconstruct-subword-deck, as well as the number of traces it uses, is
  
      (n ( 2/1-δ)^k )^O(1/(1-δ))log1/τ .
  
  
  Reconstruct-subword-deck has the following property: for any string x ∈^n, with probability at least 1-τ 
  the output of Reconstruct-subword-deck is the k-subword deck (x,k).
  
  
  <Ref> follows immediately from <Ref> and <Ref>.
  
  We note that <Ref> dominates the overall running time of <Ref>, and that <Ref> works for arbitrary strings.  
  
  
  The algorithm in <Ref>  and its analysis are relatively straightforward. To explain the main idea, we define the notion of the right (and left) extension of a string. (Starting from this point, 
    it will be convenient for us to index a string x ∈^n
    using {0, …,n-1} as x=(x_0,…,x_n-1).) 
    
   
  Given a k-bit string w = (w_0,…,w_k-1) ∈^k, a k-bit string (w_1,…,w_k-1,b) for some b ∈{0,1} is said to be a right-extension of w.
  We define left-extensions of a string similarly.
  
  
  
  At a high level, the algorithm relies on the fact that if  is obtained by a random σ-perturbation of x^, then  has useful local uniqueness properties. More precisely, for k = O(log(n /τ)/σ), a simple probabilistic argument shows that with high probability [n-k:n-1] is the unique element of (,k)  with no right-extension in (,k). Consequently, we can identify [n-k:n-1] from the k-subword deck (,k) of . This argument can be extended inductively without much difficulty to in fact identify the whole of . 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   In contrast, <Ref> is substantially more challenging. The structural results that underlie <Ref> are based on two different sets of analytic arguments. The first argument only works when δ≤ 1/2 and employs (real) Taylor series; the second argument works for the entire range of δ <1 and employs tools from complex analysis. While the first argument is more limited in scope of applicability, it is somewhat more elementary (which we see as a positive feature) and introduces a new ingredient (the so-called “generalized deletion polynomial;” see <Ref>) which might be useful in future work, and thus  we include both arguments in the paper. In this proof overview below we only describe the second argument.  
   
   
   
   
  We begin by observing that (,k) can be obtained by computing the multiplicity of occurrences of each w ∈^k in the  set (,k); we denote this multiplicity by #(w,).
   The first key step  is to define a univariate polynomial (in the variable ζ) _,w(ζ) which has the following two key properties: (i) _,w(0)= #(w,), and (ii) using traces from _δ(), we have an unbiased estimator for _,w(ζ) for ζ= δ.
   Next, observe that given traces from _δ(), we can trivially simulate traces from _δ'() for any δ' ≥δ, and hence we can get an unbiased estimator for _,w(ζ) for any ζ∈ [δ, 1]. Recall, though, that our goal is to estimate _,w(ζ) at ζ =0 and thus items (i) and (ii) above do not give us an unbiased estimator for _,w(0). 
   
   
   The most obvious idea at this point would be to do polynomial interpolation and use estimates for  _,w(ζ) for ζ∈ [δ, 1] to infer _,w(0). Unfortunately, directly applying Lagrange interpolation is too naive an approach:  to accurately estimate _,w(0), it turns out that we need _,w(ζ) for ζ∈ [δ, 1] up to error ± 2^-Θ(n). However, to estimate _,w(ζ) up to error ±κ, at least (1/κ) traces from _δ()
   are needed (<Ref>). Thus, directly applying Lagrange interpolation would require a sample complexity that grows like 2^Θ(n), which is too expensive. 
   
  Our approach is to forego Lagrange interpolation and instead (in essence) interpolate using tools from complex analysis. In particular, we prove a new structural result (<Ref>) about polynomials whose constant coefficient is not too small 
   and whose coefficients have magnitude bounded from above by a parameter m (which is set to be n^k  in
   our application given that every coefficient of _,w(ζ) is bounded by n^k).
   
   This result implies that _,w(0) (which must be an integer given that _,w(0)= #(w,))
      is uniquely determined by the values of _,w(ζ) in the interval ζ∈ [δ, 1] if these values are given up to error  n^O(-k/(1-δ)); see <Ref>. Thus, in principle  we can determine  _,w(0) by estimating _,w(ζ) for values of ζ∈ [δ, 1] to error ± n^O(-k/(1-δ)). This essentially implies that _,w(0) can be determined using 
   ≈ n^O( k/(1-δ)) traces from _δ().  (Note though that this sample complexity is not quite as good as is claimed in <Ref>. We refine the above argument, using stronger coefficient bounds on _,w and other ideas described at the beginning of <Ref>, to get  <Ref> in its full strength as stated earlier.)
    
   In closing this subsection, we emphasize that while <Ref> is about the behavior of polynomials on the real line, its proof crucially uses tools from complex analysis such as Jensen's formula and the Hadamard three circle theorem. We further note that while we have sketched above how _,w(0) can be determined in principle, this does not necessarily give an efficient algorithm.  To get an efficient algorithm, we use an approach based on linear programming. 
  
   
   
   
    
   
   
   
  
   
   
   
   
   
   
   
   
    
  
  
  
  
  
  
  
   §.§ Discussion and future work
  
  
  We view this paper as a first exploration, establishing that the algorithmic framework of smoothed analysis  can be fruitfully brought to bear on the trace reconstruction problem.  There are many interesting questions and directions for future work, some of which we highlight below.
  
  One natural question is to establish strong sample complexity lower bounds for smoothed trace reconstruction.  Currently the best lower bound we are aware of for this framework is Ω̃( log ^5/2n ) for average-case trace reconstruction due to <cit.>. Can an n^Ω(1) lower bound be established for the smoothed model?
  
  Another natural goal is to quantitatively strengthen our algorithmic result.  In the regime of σ=c/n with c a small constant, the smoothed problem reduces to the worst-case problem, and in the regime σ = 1 it reduces to the average-case problem; however, the running times of our algorithm in these regimes do not match the state-of-the-art running times for the corresponding problems that are provided in <cit.> and in <cit.> respectively. As a concrete first question along these lines, is it possible to improve the sample complexity of our algorithm from its current n^1/σ dependence on the perturbation rate to a dependence more like n^1/σ^1/3?
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § PRELIMINARIES
   
  
  Notation.
  Given a nonnegative integer n, we write [n] to denote {1,…,n}.
  Given integers a≤ b we write [a:b] to denote {a,…,b}. 
  It will be convenient for us to index a binary string x ∈^n
    using [0:n-1] as x=(x_0,…,x_n-1). Given such a string x and integers 0 ≤ a < b ≤ n-1, we write x[a:b] to denote the subword (x_a, x_a+1, …, x_b).
  
  
  
  We write ln to denote natural logarithm and log to denote logarithm to the base 2.
  
  
  We denote the set of non-negative integers by _≥ 0.
  For a vector α = (α_1, …, α_ℓ) ∈_≥ 0^ℓ, we write |α| to denote α_1 + α_2 + … + α_ℓ, and write α! to denote α_1! α_2! ⋯α_ℓ!.
  
  
  
  Subword deck. Fix a string x ∈^n and an integer k ∈ [n]. A k-subword of x is a 
   (contiguous) subword of x of length k, given by (x_a, x_a+1, …, x_a+k-1) for some a ∈ [0: n-k]. For a string w ∈^k, let #(w,x) denote the number of occurrences of w as a subword of x. We define the k-subword deck of x, denoted (x,k), to be the (n-k+1)-size (unordered) multiset of all k-subwords of x.
   We also extend the notation of #(w,x) to strings w∈{0,1,*}^k, where 
     * is the wildcard symbol:
     #(w,x) is the sum of #(w',x) over all w'∈{0,1}^k with w_i'=w_i for every w_i *. 
  
  
  
  Distributions.
  We use bold font letters to denote probability distributions and 
    random variables, which should be clear from the context.
  We write “∼” to indicate that random variable  is 
    distributed according to distribution .
  
  
  
  Deletion channel and traces.
  Throughout this paper the parameter δ:0 < δ < 1 denotes the deletion probability.  Given a string x ∈^n, we write _δ(x) to denote the distribution of the string that results from passing  x through the δ-deletion channel (so the distribution _δ(x) is supported on ^≤ n), and we refer to a string in the support of _δ(x) as a trace of x.  Recall that a random trace ∼_δ(x) is obtained by independently deleting each bit of x with probability δ and concatenating the surviving bits.[For simplicity in this work we assume that the deletion probability δ is known to the reconstruction algorithm.  We note that it is possible to obtain a high-accuracy estimate of δ simply by measuring the average length of traces received from the deletion channel.]
  
  
  
  Perturbation and smoothed analysis.. The perturbation model we consider corresponds to the standard notion of perturbation of an n-bit string which arises in the analysis of Boolean functions.  Given an n-bit string x^∈^n, a σ-perturbation of x^ is a random string ∈^n obtained by independently setting each coordinate _i to be x^_i with probability 1-σ and to be uniformly random with the remaining probability σ.  Equivalently,  is a random string that is (1-σ)-correlated with x^; in the notation of Chapter 2 of <cit.>, we may write this as “∼ N_1-σ(x^).”
  
  We recall that in the smoothed analysis framework, an initial string
    x^∈^n is selected (in what may be thought of as an adversarial manner), and then a σ-perturbation  of x^ is drawn at random from N_1-σ(x^), and the algorithm runs on instance .  The goal is to develop algorithms which, for every x^∈^n, succeed with high probability on the perturbed instance ∼ N_1-σ(x^).
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § RECONSTRUCTING PERTURBED WORST-CASE STRINGS FROM THEIR
   SUBWORD DECKS: 
  PROOF OF <REF>
   
  
  
  
  In this section we prove <Ref>:
  
  
  
   Restatement of <Ref> (Reconstructing perturbed strings from their subword decks).
  
  Let 0 < σ,η < 1.  There is a deterministic algorithm Reconstruct-from-subword-deck which takes as input the k-subword deck (x,k) of a string x ∈^n, where k = O(log(n /η)/σ), and outputs either a string in ^n or “.” Reconstruct-from-subword-deck runs in (n) time and has the following property:  For any string x^∈^n, if  is a random σ-perturbation of x^ (i.e.  is obtained by independently replacing each bit of x^ with a uniform random bit with probability σ), then with probability at least 1-η 
  the output of Reconstruct-from-subword-deck on input (,k) is the string .
  
  
  
  
  The idea of <Ref> is very simple:  a probabilistic argument shows that for any worst-case string x^, a random σ-perturbation introduces enough variability into ∼ N_1-σ(x^) so that the k-subwords comprising the k-subword deck of  can be easily pieced together in a unique way to yield  by a simple greedy algorithm. We now provide details.
  
  
  
  
  
  Given (x,k) of a string x∈^n,
    we use the following greedy algorithm to recover x:
  
  
  
    * We will store the output in y, a string of length n. 
  
    * Let w∈(x,k) be a string that fails to have a right-extension in 
    (x,k).
  (Note the only k-subword of x that can fail to have a right-extension in (x,k)
    is x[n-k:n-1].)
  If no such w exists, return ; otherwise set y[n-k:n-1]=w and ℓ=n-k.
  
    * While ℓ>0, do the following: 
    Find w∈(x,k) as a left-extension of y[ℓ:ℓ+k-1].
    (Note that if y agrees with x so far, then such a left-extension must exist.)
    If w is not unique (counted with multiplicity), return ; otherwise set y_ℓ-1=w_0 and decrement ℓ by 1.
  
    * When ℓ=0, return y.
  
  
  
  It is clear from the description of the greedy algorithm above and comments therein that
    either it returns  or there is no ambiguity (in filling in the last k bits
    and extending from there bit by bit) and x is recovered correctly as y at the end.
  We use the following definition to capture strings x on which the greedy algorithm succeeds:
  
  
   
       An n-bit string x is said to be k-good if 
  
  
  
    (i) for every j∈ [n-k], there is exactly one string in (x,k) (counted
    with multiplicity) that is a left-extension of the subword x[j:j+k-1]; and
  
  
    (ii) the subword x[n-k:n-1] does not have a right-extension in (x,k).
  
  
  
  
  
  
  To prove
  <Ref>, it remains only to establish the following claim:
  
  
  
   
      Fix any string x^∈^n.  Then for k = O ( log (n/η) /σ )
      
      _∼ N_1-σ(x^)[ is k-good] ≥ 1 - η.
   
  
  
  
  
      Let E() be the event that  is not k-good. We observe that for E() to occur, there must exist indices 0 ≤ i < j ≤ n-k+1 such that the (k-1)-subwords of  starting at positions i and j are equal, 
       i.e., [i:i+k-2] = [j:j+k-2]. 
       In particular, we have the following (where here and subsequently all probabilities are over the random draw of ∼ N_1-σ(x^)):
      
      [E()]    ≤[∃i,j  such that [i:i+k-2] = [j:j+k-2]]
         ≤∑_0≤ i < j ≤ n-k+1[[i:i+k-2] = [j:j+k-2]]. by a union bound
  
      Let E_i,j() denote the event that [i:i+k-2] = [j:j+k-2]. To prove the claim, it suffices to show that [E_i,j()] ≤η/n^2 for each fixed pair 1 ≤ i < j ≤ n-k+1.
      
  To this end, we write the probability of E_i,j() as 
  
      [_i=_j]·∏_ℓ=1^k-2[_i+ℓ=_j+ℓ|_i+h=_j+h for all h=0,…,ℓ-1].
      
  The first factor [_i=_j] is at most 1-σ/2 because for any
    fixed value b of _i, _j agrees with b after the perturbation with probability 
    at most 1-σ/2.
  The upper bound of 1-σ/2 holds for every other factor in the product. 
  For the ℓth factor, we note that for any fixed values of 
    _i,…,_j+ℓ-1 that satisfy the conditioning part 
    _i+h=_j+h for all h=0,...,ℓ-1,
    _j+ℓ agrees with the fixed value of _i+ℓ
    with probability at most 1-σ/2.
  
      
  
      
  
      
  
     
  
     
  
  
  
     
  
  
      
      Now fix indices 0 ≤ i < j ≤ n-k, and let ℓ = j-i. Assume k is odd w.l.o.g.
      Consider 2 cases:
      
          
    * ℓ≥ (k-1)/2: In this case, we upper bound [E_i,j] by
      
      [[i:i+(k-1)/2-1] = [j:j+(k-1)/2-1]]
  
      By the assumption on ℓ, all events _a=_b involved in the above expression are independent, hence we have
      
      [[i:i+k-2] = [j:j+k-2]] ≤ (1-σ)^(k-1)/2≤exp(-3 log n) = 1/n^3.
  
      
      
    * ℓ < (k-1)/2: Let α be the largest integer satisfying 2αℓ≤ k-1, and let d = k-1- 2αℓ. Recall that j=i+ℓ. We can upper bound [E_i,j] by
      
      [   [i:i+ℓ-1]=[i+2ℓ:i+2ℓ-1]  and 
         [i+2ℓ:i+3ℓ-1]=[i+3ℓ:i+4ℓ-1]  and 
         …
         [i+2(α-1)ℓ:i+(2α-1)ℓ-1]=[i+(2α-1)ℓ:i+2αℓ-1]  and 
         [i+2αℓ:i+2αℓ+d-1]=[i+(2α+1)ℓ:i+(2α+1)ℓ+d-1] ]
  
      We observe that all bit-wise equality events involved in the above expression are independent. Moreover, the number of pair of comparisons is at least (k-1)/2. Thus, we have
      
      [E_i,j] ≤ (1-σ)^(k-1)/2≤exp(-3 log n) = 1/n^3.
  
      
      
  
  Now fix indices 0 ≤ i < j ≤ n-k, and let ℓ = j-i. Clearly, if ℓ≥ k-1, then the events _i+a = _j+a for a ∈ [0,k-2] are mutually independent, and so [E_i,j()] ≤ (1-σ/2)^k-1.
  
  Otherwise, let α≥ 1 be the largest integer satisfying (2α-1) ℓ≤ k-1. 
  We can upper bound [E_i,j()] by
      
      [   [i:i+ℓ-1]=[i+2ℓ:i+2ℓ-1]  and 
         [i+2ℓ:i+3ℓ-1]=[i+3ℓ:i+4ℓ-1]  and 
         …
         [i+2(α-1)ℓ:i+(2α-1)ℓ-1]=[i+(2α-1)ℓ:i+2αℓ-1]
  
      We observe that all bit-wise equality eventsNeed better phrasing for each bit-wise equality test. involved in the above expression are independent. Moreover, the total number of comparisons is at least
      
      αℓ > α/2 α + 1 (k-1) ≥k-1/3,
  
      where we have used the maximality of α and that α≥ 1. 
      
      
      
  
  Thus, by setting k=Clog (n/η) / σ for some large enough constant C, we have 
      
      [E_i,j()] ≤ (1-σ/2)^k-1≤exp(-Ω(logn/η)) ≤η/n^2.
  
  This finishes the proof of the claim.
  
  
  
  
  
  
  
  
  
  
  
  
  § RECONSTRUCTING THE K-SUBWORD DECK:  PROOF OF <REF>
   
  
  
  The remaining task to establish the main result, <Ref>, is to prove <Ref> (restated below), which gives an efficient algorithm to reconstruct the k-subword deck of an arbitrary source string x ∈^n given access to independent traces of x. Throughout this section, let ρ = (1-δ)/2.
  
  
  
  Restatement of <Ref> (Reconstructing the k-subword deck).
  
  Let 0 < δ,τ' < 1.  There is an algorithm Reconstruct-subword-deck which takes as input a parameter 
  1 ≤ k ≤ n
  and access to independent traces of an unknown source string x ∈^n.
  The running time of Reconstruct-subword-deck, as well as the number of traces it uses, is
  
      ( n/ρ^k)^O(1/ρ)log (1/τ').
  
  Reconstruct-subword-deck has the following property:  For any unknown string x ∈^n, with probability at least 1-τ', 
  Reconstruct-subword-deck
    outputs (x,k).
  
  
  
  
  The main algorithmic ingredient that underlies <Ref> is an algorithm for a closely related but slightly simpler problem. This algorithm, which we call Multiplicity, takes as input a string w ∈^k and access to independent traces from an unknown source string x, and it outputs #(w,x), the multiplicity of w in the (n-k+1)-element multiset (x,k) (note that this multiplicity can be zero if w is not present as a subword of x):
  
   
  Let 0 < δ,τ < 1 and let ρ = (1-δ)/2. There is an algorithm Multiplicity which takes as input a string w ∈^k 
  and access to independent traces of an unknown source string x ∈^n.
  Multiplicity runs in (n / ρ^k)^O(1/ρ)log (1/τ) 
  time and uses (n / ρ^k)^O(1/ρ)log (1/τ)
  
  many traces from _δ(x), and has the following property:  For any unknown source string x ∈^n, with probability at least 1-τ   
  the output of Multiplicity is #(w,x) (i.e. the number of occurrences of w as a subword of x).
  
  
  
  A standard “branch-and-bound” argument gives <Ref> from <Ref>:
  
  
  
  
  Proof of <Ref> using <Ref>.
  Let ℓ=⌊log n⌋. We first consider the case that k ≤ℓ.  In this case Reconstruct-subword-deck simply runs Multiplicity(w) once for each of the 2^k strings w ∈^k, with the confidence parameter “τ” for each run of Multiplicity set to τ'/2^k. Since we can reuse the same traces for each of the 2^k runs, in this case the running time is 2^k (n / ρ^k)^O(1/ρ)log (2^k/τ') = (n / ρ^k)^O(1/ρ)log (1/τ')  
  and the sample complexity is
  (n / ρ^k)^O(1/ρ)log (1/τ').
  
  
  
  
  Next we consider the case that k > ℓ.  To avoid an exponential running time dependence on k, the algorithm uses a simple “branch-and-prune” approach.  In the first stage, similar to the previous paragraph, Reconstruct-subword-deck runs Multiplicity on each of the 2^ℓ strings w ∈^ℓ with confidence parameter τ'/(2nk), thereby obtaining the ℓ-subword deck (x,ℓ).  It then executes k - ℓ many successive stages j=1,2,…,k-ℓ, where in stage j the algorithm determines the (ℓ + j)-subword deck of x using the (ℓ + j-1)-subword deck of x. It does this in each stage as follows:  for each of the (at most n) distinct strings w ∈(x,ℓ + j - 1), the algorithm runs Multiplicity(w0) and Multiplicity(w1), each with confidence parameter τ'/(2nk).
  
  The correctness of this approach follows from the trivial fact that an (ℓ+j)-bit string can only be present in (x,ℓ+j) if its (ℓ+j-1)-bit prefix is present in (x,ℓ+j-1). Since there are at most 
  n + 2n(k-ℓ) < 2kn
  
  many runs of Multiplicity overall, the running time of Reconstruct-subword-deck is at most O(kn) ·(n / ρ^k)^O(1/ρ)log (2kn/τ') = (n / ρ^k)^O(1/ρ)log (1/τ') 
  
  
  and the sample complexity is at most
  (n / ρ^k)^O(1/ρ)log (1/τ'), 
  
  
  
  and <Ref> is proved. 
  
  
  
  
  Thus, in the rest of the paper, we focus on proving <Ref>. 
  
  
  
   §.§ The subword polynomial
  
  
  The following “subword polynomial” plays an important role in our approach:
  
  
  
  
  Fix a string x ∈^n, integers k ∈ [n], ℓ∈ [n-k], and a word w ∈^k. 
  Let f(x,w,ℓ) be the number of occurrences of the word
  
      w' = ∗^α_0 w_0 ∗^α_1 w_1 ∗^α_2 w_2 … w_k-2∗^α_k-1 w_k-1
  
  in x, where α_i ≥ 0, ∑_i=1^k-1α_i = ℓ, and each ∗ is either 0 or 1. Note that f(x,w,0) is precisely the frequency of w as a subword of x. We can express f(x,w,ℓ) as
  
      f(x,w,ℓ) = ∑_α∈_≥ 0^k, |α| ≤ n-k
       |α|-α_0 = ℓ x_α_0 = w_0, x_α_0+α_1+1=w_1, ⋯, x_α_0 + ⋯ + α_k-1 + k-1 = w_k-1.
  
  
  Let P_x,w(ζ) be the following univariate polynomial of degree n-k:
  
      P_x,w(ζ) = ∑_α∈_≥ 0^k-1, |α| ≤ n-k f(x,w,|α|-α_0)  ζ^|α|-α_0
  
  
  
  
  
  Fix a string x ∈^n, an integer k ∈ [n], and a word w ∈^k. For α∈_≥ 0^k-1 with |α| ≤ n-k, we define f(x,w,α) to be the number of occurrences of the word
  
      w' = w_0 ∗^α_1 w_1 ∗^α_2 w_2 … w_k-2∗^α_k-1 w_k-1
  
  in x, where each ∗ is either 0 or 1. 
  
  
  
  We can express f(x,w,α) as
  
      f(x,w,α) = ∑_0 ≤ i ≤ n-k-|α|+1(x_i, x_i+α_1+1, ⋯, x_i+α_1 + ⋯ + α_k-1 + k-1) = w.
  
  
  
   
  Given x ∈^n and w=(w_0,…,w_k-1) ∈^k, let _x,w(ζ) be the following univariate polynomial of degree n-k:
  
      _x,w(ζ) := ∑_α∈_≥ 0^k-1
       |α| ≤ n-k #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1, x)  ·ζ^|α|.
  
  
  
  In words, the degree-ℓ coefficient of the subword polynomial _x,w is the number of ways that w arises as a substring of x with a total of exactly ℓ extraneous additional characters interspersed among the characters of w. In particular, we have that the constant term of _x,w (i.e. _x,w(0), since 0^0=1) is equal to #(w,x), the frequency of w as a subword of x, which is what <Ref> aims to estimate efficiently from traces of x. 
  
  
  
   §.§ Outline of our approach
  
  
  We prove <Ref> by giving two different algorithms depending on the value of the deletion rate δ.
  The first of these algorithms, Multiplicity_small-δ, gives a simple and direct approach to compute the value _x,w(0) =#(w,x); however this approach requires the deletion rate δ to be less than 1/2. 
  This approach is based on analyzing a new object, the “generalized deletion polynomial,” that we believe may be useful for subsequent work.  
  The second of these algorithms, Multiplicity_large-δ, gives a different and somewhat more involved algorithm (involving linear programming and a new extremal result on polynomials, proved using complex analysis) that can be used for any deletion rate δ<1.  
  
  Readers who are  interested in a simple analysis (albeit one that works only for δ <1/2)
    may wish to focus on Multiplicity_small-δ (<Ref>).
  Readers who are  interested in a more involved approach that succeeds for all δ<1 may wish to focus on Multiplicity_large-δ (<Ref>).  The two algorithms and analyses are each self-contained; each may be read independently of the other. 
  
  
  For each of the two algorithms, 
    we first give a simpler version of the analysis which establishes a quantitatively weaker version of the result, with an n^O(k) running time and sample complexity (ignoring the dependence on other parameters); see the statements of <Ref> and <Ref>, at the beginnings of <Ref> and <Ref> respectively, for detailed statements of these weaker versions.  In <Ref> we quantitatively strengthen both  <Ref> and <Ref> to achieve a (n) ·exp(O(k)) running time and sample complexity, and thereby complete the proof of <Ref>.
   
  
  
  
  
  
  
  § MULTIPLICITY'_SMALL-Δ:  AN ALGORITHM FOR DELETION RATE Δ <1/2
  
  
  
  
  In this section we prove <Ref>,
    a weaker version of <Ref>.
  It gives an algorithm that has n^O(k) running time and sample complexity (ignoring the dependence on other parameters) and works when δ < 1/2.
  Actually <Ref> works when δ≤ 1/2;
    we only require δ < 1/2 later in <Ref> 
    to achieve
    the improved running time and sample complexity in <Ref> based on a similar approach (the running time achieved in that section will depend on how close δ is to 1/2).
    
    
  
  
  
  
  
   
  Let 0 < δ≤ 1/2. 
  
  There is an algorithm  Multiplicity'_small-δ which takes as input a string w ∈^k, access to independent traces of an unknown source string x ∈^n, and a parameter τ>0.
  Multiplicity'_small-δ draws n^O(k)·log (1/τ) traces from _δ(x), runs in time n^O(k)·log (1/τ),  and has the following property:  For any unknown source string x ∈^n, with probability at least 1-τ 
  the output of Multiplicity'_small-δ is the multiplicity of w in (x,k) (i.e. the number of occurrences of w as a subword of x). 
  
  
  In <Ref> we will build on <Ref> to give a stronger version that has (n) ·exp(O(k)) running time and sample complexity (ignoring the dependence on other parameters) for δ < 1/2.
  
  The rest of this section is organized as follows. In <Ref>, we give an equivalent expression for _x,w(ζ) in <Ref>,
    which relates the subword polynomial to traces drawn from the deletion channel.
  The proof uses the generalized deletion polynomial and is presented in
    <Ref>.  
  This new expression for _x,w(ζ) allows one to 
    evaluate _x,w(ζ) at ζ=0   
    up to a small error (say, ± 0.1) using traces of x (see Corollary <ref>)
    when δ≤ 1/2.
  Given that _x,w(0) is an integer, 
    the result can be rounded to obtain the exact value of _x,w(0);
    this finishes the proof of <Ref>. 
    
  We remark that the expression for _x,w(ζ) given in <Ref>
    works for any ζ∈, when viewing  _x,w(ζ) as a polynomial over ,
    and may be useful for subsequent work. 
  Indeed Corollary <ref> shows that _x,w(ζ) can be evaluated at any 
    ζ∈ B_1-δ(δ) up to a small error
    using traces of x,
    where B_1-δ(δ) denotes the complex disc with center 
    δ and radius 1-δ.
  We need δ≤ 1/2 so that 0∈ B_1-δ(δ).
    
  
  
  
  
   §.§ Evaluating _x,w(ζ) for  ζ∈ B_1-δ(δ) using traces of x
   
  
  
  
  In the rest of this section we consider _x,w(ζ) as a polynomial over complex numbers.
  The main technical ingredient in the algorithm Multiplicity'_small-δ is the following theorem, which relates the subword polynomial to traces drawn from the deletion channel:
  
  
      
      Let x, k and w be as above. Then for all ζ∈
      
      we have
      
      _x,w(ζ) = 1/(1-δ)^k ∑_α∈_≥ 0^k-1
       |α| ≤ n-k _∼_δ(x)[ #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1,) ]·( ζ-δ/1-δ)^|α|.
  
  
  
  Before proving <Ref> in <Ref> we use it to obtain
    the following corollary. 
  
  
   
      Let x,k,w be as above, and let > 0. Then, given access to traces ∼_δ(x), there exists an algorithm which, given as input any ζ∈ B_1-δ(δ), evaluates _x,w(ζ)  up to error ± with success probability at least 1 - τ. The algorithm takes
      
      (n/1-δ)^O(k)·1/^2·log(1/τ)
   many traces and running time.
  
  
  Recall that _x,w(0) = #(w,x).
   When δ≤ 1/2, the disc B_1-δ(δ) contains the origin.  Therefore, setting = 1/3 in Corollary <ref> directly implies an algorithm Multiplicity'_small-δ   that 
   
   uses
    ((n / (1-δ))^O(k) ) ·log (1/τ) = n^O(k)·log (1/τ) traces 
     and running time to evaluate _x,w(0) up to an error of =1/3,
    which succeeds with probability at least 1-τ. 
  It then rounds the result to the nearest integer to obtain _x,w(0)=#(w,x) given that the latter
    is an integer. 
  This finishes the proof of Theorem <ref>.
  
  
  The algorithm simply draws 
      s=(n/1-δ)^O(k)·1/^2·log(1/τ)
   many traces _1,
    …,_s of x and uses them to compute an empirical estimate Ẽ_α of
  
      E_α:=_∼_δ(x)[ #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1,) ]
   
  for each α∈_≥ 0^k-1 with |α| ≤ n-k.
  This is done by computing #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1,_i)
    for each α and _i (in time polynomial in n)
    for each pair of α and _i),
    and then taking the average over _1,…,_s for each α.
  Given that the number of α's is at most n^k, the overall running time is 
    s· n^k·(n),
    as stated in Corollary <ref>.
    
  
  
  
  Given that #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1,) in (<ref>) is between 0 and n, 
    it follows from our choice of s, a Chernoff bound and a union bound, that with probability at least 1-τ,
    every empirical estimate Ẽ_α satisfies
    
      |Ẽ_̃α̃-E_α|≤·(1-δ/n)^k .
  
    
  Using 
  
      |ζ-δ/1-δ|≤ 1
  
  when ζ∈ B_1-δ(δ), we can use Ẽ_α to obtain an estimate of
    _x,w(ζ):
  
      1/(1-δ)^k∑_αẼ_α·( ζ-δ/1-δ)^|α|
  
  and the estimate is correct up to error 
  
      1/(1-δ)^k∑_α |Ẽ_α -E_α|≤,
  
  where the inequality holds by <Ref> given that the number of α's is no more than n^k.
  
  
  
  
  
  
  
  
  
   §.§ Generalized deletion polynomial and the proof of <Ref>
  
  
  
  
  In this subsection we prove <Ref>. 
  We first introduce a more general class of polynomials, the (x,f)-deletion-channel polynomials 
    (see  <Ref>), of which _x,w is a special case.
  We then prove an extension of <Ref> (see <Ref>)
    which applies to 
    every (x,f)-deletion channel polynomial; <Ref> follows as a direct corollary.
   
  While we don't need the full generality of <Ref> to 
    prove <Ref>,
  
    working with this new class of polynomials makes our proofs cleaner.
  We also believe that <Ref> in the general form
    may be useful for subsequent analysis.
  
  The following notation will be convenient for us. Given vectors γ∈_≥ 0^k and ξ∈^k, and a function P(z_1,…,z_k) from ^k to , we define 
  
      ξ^γ = ξ_1^γ_1⋯ξ_k^γ_k    and     D^γ P = ∂^γ P/∂ z_1^γ_1⋯∂ z_k^γ_k .
  
  Recall that γ! = γ_1! ⋯γ_k! and γ = γ_1 + ⋯ + γ_k.
  
  For v ∈, we will denote the vector (v, v, ⋯, v) ∈^k by v⃗, where the dimension k will be clear from context.
  
  We define the class of (x,f)-deletion-channel polynomials:
    
      Given f^k → and a string x ∈^n, the (x,f)-deletion-channel polynomial P_x,f^k → is defined by
      
      P_x,f(ξ) := ∑_γ∈_≥ 0^k
      γ≤ n - k f(x_γ_1, x_γ_1 + γ_2 + 1, …, x_γ_1 + … + γ_k + (k-1))·ξ^γ .
  
    
  
  
  
  
  
  
  We call P_x,f the (x,f)-deletion-channel polynomial because by choosing
     k=1 and f → to be the 1-bit identity function 𝕀(x) = x, we have that
    
      P_x,𝕀(ξ) = ∑_i=0^n-1 x_i ξ^i
  
    is the deletion-channel polynomial defined in <cit.>. 
  
  
    The next theorem shows that under a change of variables, the coefficients of P_x,f with respect to the new variables can be expressed in terms of the expectation of f over traces of x drawn from the deletion channel. We state it and then show that <Ref> follows as a direct corollary. 
  
     
      For any ξ∈^k, we have
      
      P_x,f(ξ) = 1/(1-δ)^k ∑_β∈_≥ 0^k
      β≤ n - k_∼_δ(x)[ f(_β_1, …, _β_1 + … + β_k + k - 1) ] ·( ξ - δ⃗/1-δ)^β.
  
    
  
  
  
  
    
      Given x ∈^n and w ∈^k for some k ∈ [n] as in the statement of <Ref>,
      we take f : ^k → to be the indicator function of w:
      
      f(b_1, b_2, …, b_k) = (b_1, b_2, …, b_k) = w.
  
  Using this f we get the following connection between _x,w(ζ) and P_x,f(1,ζ,
    ζ,…,ζ):
      
      _x,w(ζ)    = ∑_α∈_≥ 0^k-1
       |α| ≤ n-k #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1, x)  ·ζ^|α|
         = ∑_α∈_≥ 0^k-1
       |α| ≤ n-k∑_i=0^n-k-|α|  f(x_i, x_i+α_1+1, x_i + α_1 + α_2+2, …, x_i + |α| + k-1)   1^i  ζ^|α| 
              = P_x,f(1, ζ, ζ, ⋯, ζ)
  
  Applying <Ref> on P_x,f(1, ζ, ζ, …, ζ), we have
  
      _x,w(ζ)   = 1/(1-δ)^k ∑_α∈_≥ 0^k-1
       |α| ≤ n-k∑_i=0^n-k-|α|_∼_δ(x) [ f(_i, _i+α_1+1, …, _i + |α| + k-1) ]
              ·( ζ - δ/1-δ)^|α|
         = 1/(1-δ)^k ∑_α∈_≥ 0^k-1
       |α| ≤ n-k _∼_δ(x)[ #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1, ) ] ·( ζ-δ/1-δ)^|α|
  
    where the last step follows by linearity of expectation. This concludes the proof of <Ref>.
    
  
    We now prove <Ref>.  The high-level idea is to relate the expectation of f over traces of x drawn from the deletion channel to partial 
    derivatives of polynomial P_x,f at δ⃗, and then apply Taylor's expansion to P_x,f at the point δ⃗.
  
  
     
      Let β∈_≥ 0^k with  β≤ n - k.
      We have
      
      _∼_δ(x)[ f(_β_1, …, _β_1 + … + β_k + (k-1)) ]
            = (1 - δ)^k ·(1-δ)^β/β!· D^β P_x,f(δ⃗) .
  
    
  
    To get some intuition, consider the special case of k=1 (so P_x,f is univariate) and f = 𝕀. Then it is straightforward to verify that
    
      _∼_δ(x)[_0] = (1-δ) ∑_i=0^n-1 x_i δ^i = (1-δ) · P_x,𝕀(δ) ,
  
    and
    
      _∼_δ(x)[_1]
          = (1-δ) ∑_i=1^n-1 x_i i1 (1-δ) δ^i-1
          = (1-δ)^2 ∑_i=1^n-1 x_i i δ^i-1
          = (1-δ)^2 · D^1 P_x,𝕀(δ).
  
  
    
      For a fixed γ∈_≥ 0^k with |γ| ≤ n-k, we write
      
      γ→β,
                or equivalently      (γ_1, γ_2, …, γ_k) → (β_1, β_2, …, β_k),
  
      to denote the event that 
      the (γ_1, γ_1 + γ_2 + 1, …, γ_1 + … + γ_k + (k-1)) positions of x become the (β_1, β_1 + β_2 + 1, …, β_1 + … + β_k + (k-1)) positions of ∼_δ(x) respectively.  For this to occur, each bit x_γ_i must be present in , which happens with probability (1-δ)^k.  Further, for each x_γ_i to become _β_i, exactly β_i out of the γ_i bits between (and including) positions γ_1 + ⋯ + γ_i-1 + i and γ_1 + ⋯ + γ_i + (i-1) of x must be retained. So, the probability of this event is
      
      [γ→β]
               = 
            
            (1-δ)^k ∏_i=1^k γ_iβ_i (1-δ)^β_iδ^γ_i - β_i
         = (1-δ)^k ∏_i=1^k γ_i (γ_i-1) ⋯ (γ_i - β_i + 1)/β_i! (1-δ)^β_iδ^γ_i - β_i
         = (1-δ)^k ·( ∏_i=1^k (1-δ)^β_i/β_i!) ·∏_i=1^k (γ_i (γ_i-1) ⋯ (γ_i - β_i + 1) ·δ^γ_i - β_i) 
         = (1-δ)^k ·(1-δ)^β/β!·∏_i=1^k d^β_i/d δδ^γ_i.
      
      
      The factor (1-δ)^k is because the bits x_γ_i must be present in . Then to retain each x_γ_i so that it becomes y_β_i, we can retain β_i out of the γ_i bits between positions γ_1 + ⋯ + γ_i-1 + i and γ_1 + ⋯ + γ_i + (i-1) of x.
      Now,
      
      _∼_δ(x) [ f(_β_1, …, _β_1 + … + β_k + (k-1)) ]
            = ∑_γ≤ n-k f(x_γ_1, …, x_γ_1 + ⋯ + γ_k + (k-1)) [γ→β] .
  
      For a fixed γ, 
      
      [γ→β]
               = (1-δ)^k ∏_i=1^k γ_iβ_i (1-δ)^β_iδ^γ_i - β_i
         = (1-δ)^k ∏_i=1^k γ_i (γ_i-1) ⋯ (γ_i - β_i + 1)/β_i! (1-δ)^β_iγ^γ_i - β_i
         = (1-δ)^k ·( ∏_i=1^k (1-δ)^β_i/β_i!) ·∏_i=1^k γ_i (γ_i-1) ⋯ (γ_i - β_i + 1) δ^γ_i - β_i
         = (1-δ)^k ·(1-δ)^β/β!·∏_i=1^k d^β_i/d δδ^γ_i .
  
      
  As a result, we have that
      
      _∼_δ(x)[ f(_β_1, …, _β_1 + … + β_k + (k-1)) ] 
         = ∑_γ≤ n-k f(x_γ_1, …, x_γ_1 + ⋯ + γ_k + (k-1))·[γ→β] 
         = (1-δ)^k ·(1-δ)^β/β!∑_γ≤ n-k f(x_γ_1, …, x_γ_1 + ⋯ + γ_k + (k-1))·∏_i=1^k d^β_i/d δδ^γ_i<Ref>
         = (1-δ)^k ·(1-δ)^β/β!· D^β P_x,f(δ⃗).
  
  This finishes the proof of Claim <ref>.
    
  
    
  Since P_x,f is a polynomial of degree at most n-k,
      applying Taylor's expansion to P_x,f at the point δ⃗ and using Claim <ref>, we get that
    
      (1-δ)^k·  P_x,f(ξ)
             = (1-δ)^k ∑_β≤ n - kD^βP_x,f(δ⃗)/β!· (ξ - δ⃗)^β
         = ∑_β≤ n - k_∼_δ(x)[ f(_β_1, …, _β_1 + … + β_k + k - 1) ]·( ξ - δ⃗/1-δ)^β.
  
    
    
  
  
    Applying Lemma <ref> to _x, we have
    
      (1-δ)^2 _x(ξ_1, ξ_2) = ∑_0 ≤ j_1 + j_2 ≤ n-2_∼_δ(x)[_j_1∧_j_1 + j_2 + 1] ( ξ_1-δ/1-δ)^j_1( ξ_2-δ/1-δ)^j_2.
  
    As we can do empirical estimate of [_j_1∧_j_2], we can estimate _x(ξ) for any ξ∈ D_1-δ(δ)^2 := {(ξ_1, ξ_2) ∈^2 : ξ_i - δ≤ 1-δ for i ∈{1,2}}.
  
  
    In subword-counts2.pdf, we fix ξ_1 = 1 and look at the univariate polynomial in ξ_2 defined by
    
      _x(ξ_2)
          := _x(1, ξ_2)
             = ∑_i_2=0^n-2∑_i_1=0^n-2-j_2 x_i_1 x_i_1+i_2+1ξ_2^i_2
         = ∑_i_2=0^n-2#( 1 ^i_2 1;x) ξ_2^i_2 .
  
    Using the expression of _x(1,ξ_2) above, we can write _x(ξ_2) as
    
      (1-δ)^2 _x(ξ_2)
             = ∑_j_2 = 0^n-2∑_j_1=0^n-2-j_2_∼_δ(x)[_j_1∧_j_1 + j_2 + 1] ( ξ_2-δ/1-δ)^j_2
         = ∑_j_2 = 0^n-2_∼_δ(x)[ ∑_j_1=0^n-2-j_2 (_j_1∧_j_1 + j_2 + 1) ] ( ξ_2-δ/1-δ)^j_2
         = ∑_j_2 = 0^n-2_∼_δ(x) [ #(1 ^j_2 1; ) ] ( ξ_2-δ/1-δ)^j_2 .
  
    
    To distinguish two distinct strings x and x', again it suffices to show that the quantity _x(ξ) - _x'(ξ) = _x-x'(ξ) is large for some ξ∈ D_1-δ(δ).
    Note that _x-x'(ξ) is a univariate polynomial where the ith coefficient is an integer between -(n-i-1) and (n-i-1), and since x  x', we know that one of the coefficients must be nonzero.
    Again we can apply the Borwein and Erdélyi result, i.e. Theorem <ref>, to an arc that lies in D_δ(1-δ),
    but in this case we take the parameter M in the theorem to be n instead of 1, which gives a worse lower bound compared to the k=1 case.
  
    Quick-calculations-for-subwords.pdf considered the special case where the 0-th coefficient of _x-x'(ξ) must be nonzero.
    It shows that _x-x'(ξ) ≥ n^-O(1/θ) for some θ∈ [δ,1].
    In fact, for this case,  we can also apply Theorem <ref> to get the same lower bound of exp(-log n/θ) = n^-O(1/θ), but here the maximum is taken over the larger domain of D_1-δ(δ).
  
  
  
  
  
  
  
  § MULTIPLICITY'_LARGE-Δ:  AN ALGORITHM FOR DELETION RATE Δ < 1
   
  
  In this section we prove a weaker version of <Ref>, giving an algorithm that works for any
    deletion rate δ < 1 but has quasipolynomial running time and sample complexity when k ≈log n (as will be the case in our ultimate application):
  
    
  Let 0 < τ,δ < 1. There is an algorithm 
  Multiplicity'_large-δ which takes as input a string w ∈^k and access to independent traces of an unknown source string x ∈^n.
  Multiplicity'_large-δ runs in  (n^1/(1-δ)/1-δ)^O(k)log(1/τ) 
  time and uses (n^1/(1-δ)/1-δ)^O(k)log(1/τ)  
  many traces from _δ(x), and has the following property:  For any unknown source string x ∈^n, with probability at least 1-τ 
  the output of Multiplicity'_large-δ is #(w,x), the multiplicity of w in (x,k) (equivalently, the value _x,w(0)).
  
  
  Looking ahead, in <Ref> we will build on the proof of 
  <Ref> to give a stronger version that has polynomial running time and sample complexity when k ≈log n.
   
  
  The following result is central to our analysis.  Informally, it says that if q is a polynomial with “not-too-large” coefficients and a constant term which is bounded away from _x,w(0) by at least 1/2, 
  then q must “differ noticeably” from _x,w over a particular interval. (Looking ahead, for our purposes it is crucially important that this interval corresponds to a range of deletion probabilities for which it is easy to estimate the polynomial's value given access to traces drawn from _δ(x).)
  
  
  
   
      Fix strings x ∈^n, w ∈^k for some k ∈ [n]. Let q(z) = ∑_ℓ=0^n-k q_ℓ  z^ℓ be any polynomial such that |_x,w(0) - q(0)| ≥ 1/2, 
      and 0 ≤ q_ℓ≤ n^k 
      for all ℓ∈{0,1,⋯,n-k}. 
      
      Then 
  
      sup_ζ∈ [δ,(δ+1)/2]|_x,w(ζ) - q(ζ) |≥ n^-O(k/(1-δ)),  for any δ∈ (0,1).
  
  
  
  
   
      Let x, x' ∈^n be distinct strings such that #(w,x) ≠#(w,x') for some k ∈ [n], w ∈^k. 
      Then for any δ∈ (0,1),
      
      sup_ζ∈ [δ,(δ+1)/2]|_x,w(ζ) - _x',w(ζ) |≥ n^-O(k/(1-δ)).
  
  
  
  
  
  
  <Ref> is an easy consequence of the following more general theorem:
  
    
  Let 1 ≤ n ≤ m.  Let p(z) = ∑_ℓ=0^n p_ℓ  z^ℓ be a polynomial of degree at most n with real coefficients such that |p_0| ≥ 1/2, and |p_ℓ|≤ m for all ℓ. Then we have 
  
      sup_ζ∈ [δ,(δ+1)/2]|p(ζ)| ≥ m^-O(1/(1-δ)),  for any δ∈ (0,1).
  
  
  
  
  To obtain <Ref>  from <Ref>, set p = _x,w - q. By the condition of <Ref> we have that |p_0| = |_x,w(0) - q_0| ≥ 1/2. Writing (_x,w)_ℓ for the degree-ℓ coefficient of _x,w, from the discussion following <Ref> it is immediate that 0 ≤ (_x,w)_ℓ≤n  k≤ n^k, and hence |p_ℓ| = |(_x,w)_ℓ - q_ℓ| ≤ n^k. 
  Thus we can invoke <Ref> with m=n^k to obtain <Ref>.
  
  In <Ref> we present and analyze the algorithm Multiplicity'_large-δ (which is based on 
    linear programming) and prove <Ref> assuming <Ref>.
  The proof of <Ref>, which is based on complex analysis, is given in <Ref>. 
  
  
  
  
  To see that <Ref> follows from <Ref>, set p = _x,w - _x',w. Then |p(0)| = |#(w,x) - #(w,x')| ≥ 1. Moreover, we have |p_i| ≤ n^k for all i ∈{0,1,⋯,n} because the number of terms α∈_≥ 0^k-1 satisfying |α| = i is at most n^k-1, and the quantity in each term is bounded between -n and n. So, we can invoke <Ref> with m=n^k to obtain <Ref>.
  
  
  
  
      Fix any deletion rate δ > 0. For any position j ∈ [0,n-k-1] and vector β∈_≥ 0^k-1 with |β|≤ n-j, we have
      
      _∼_δ(x)[(_j, _j+β_1+1, ⋯, _j + β_1 + ⋯ + β_k-1 + (k-1)) = w] = ???.
  
  
  
  
  
  
  
   §.§ Proof of <Ref> assuming <Ref>
   
  
  
  
    §.§.§ Estimating _x,w(δ') 
  for 
  δ' ≥δ
  
  The following easy lemma gives an unbiased estimator for _x,w(δ'), for all δ' ≥δ, 
  given traces from _δ(x). 
   
  Let x ∈^n, w ∈^k and let ϵ>0. Then, given traces ∼_δ(x), there 
  exists an algorithm, which for any δ' ∈ [δ,1], 
  evaluates _x,w(δ') up to error ±ϵ with success probability at least 1-τ. The algorithm takes 
  
      n^O(1)·( 1/1-δ')^O(k)·1/ϵ^2·log( 1/τ)
  
  many traces and running time. 
  
  
  First of all, observe that given ∼_δ(x), we can sample ∼_δ'(x) for any δ' ≥δ with no overhead. 
  
  
  
  Next, observe that the expected number of w in a randomly trace ∼_δ'(x) is given by 
  
      _∼_δ'(x)[#(w,)] =
        ∑_α∈_≥ 0^k-1
       |α| ≤ n-k #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1, x)  ·δ'^|α|· (1-δ')^k.
  
  This follows from the fact that every occurrence of w as a subword of trace y  can be uniquely identified with a  subsequence (i_1≤…≤ i_k) such that  (i) 
  x_i_1=w_1 ∧…∧ x_i_k=w_k. (ii) positions i_1, …, i_k are not deleted in .  (iii) every position in [i_1, …, i_k] ∖{i_1, …, i_k} is deleted in the trace .  However, by <Ref>, it follows that 
  
      _∼_δ'(x)[#(w,)]
         = _x,w(δ') · (1-δ')^k.
  
  Now for any ∼_δ'(x), 
  #(w,) is an integer between 0 and n. Thus, the standard empirical estimator will use 
  
      n^O(1)·( 1/1-δ')^O(k)·1/ϵ^2·log( 1/τ)
  
  many traces and running time and returns an estimate of 
  _∼_δ'(x)[#(w,)] up to ±ϵ· (1-δ')^k. Using (<ref>), we get the claim. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
    §.§.§ The Multiplicity'_large-δ algorithm and its analysis
  
  
  
  
  We present the algorithm Multiplicity'_large-δ in <Ref>. 
  For its correctness we first observe that with probability at least 1-τ, 
  we have that 
  
      for 
        every ζ∈ S,  |_x,w(ζ) -_x,w(ζ)| ≤κ/5.
  
    
  We finish the proof by showing that when this happens, 
    the linear program in lines 3(a) and 3(b) is feasible,
    and furthermore, |q_0-_x,w(0)|<1/2 in any feasible solution (q_0,…,q_n-k) (when this happens, the closest integer to q_0
      is exactly _x,w(0)).
    
    To see that the linear program is feasible, we let p_0,…,p_n-k denote the coefficients of _x,w, so
    
    _x,w(ζ)=∑_ℓ=0^n-k p_ℓζ^ℓ.
  
  
  
   
   From the discussion after <Ref>, every p_ℓ lies between 0 and 
     n^k.
  As a result, p_0,…,p_n-k is a feasible solution to the linear program 
    because for every ζ∈ S,  
  
      |∑_ℓ=0^n-k 
      p_ℓζ^ℓ - _x,w(ζ)|= 
      |_x,w(ζ) - _x,w(ζ)|≤κ/5.
  
     
  
  
  
   
  Next we let q_0, …, q_n-k be any feasible solution to the linear program
    and assume for a contradiction that 
  |q_0-_x,w(0)|≥1/2.  
  Let q be the polynomial q(ζ)=∑_ℓ=0^n-k q_ℓζ^ℓ.
    
  
  
  
  
  
  Given that 0≤ q_ℓ≤ n^k for every ℓ (as required by the linear program), 
    <Ref> implies (using the choice of κ in
  line 1 of the algorithm) that
  
      sup_ζ∈ [δ,(δ+1)/2]|_x,w(ζ) - q(ζ) |≥κ.
  
  The following claim (with s=_x,w -q and m=n^k) 
    shows that there exists a ζ∈ S
    such that 
  
      |_x,w(ζ) - q(ζ) |≥κ/2,
  
  a contradiction to the assumption that q_0,…,q_n-k is a feasible solution
    because
  
      |∑_ℓ=0^n-k 
      q_ℓζ^ℓ - _x,w(ζ)|
      =|q(ζ)- _x,w(ζ)|≥|q(ζ)-_x,w(ζ)|-|_x,w(ζ)-_x,w(ζ)|
      >κ/5.
  
  
    [Searching over S suffices] 
  Let 
  s(t) = s_0 + s_1 t + ⋯ + s_n t^n
  be a polynomial such that  every coefficient s_ℓ has |s_ℓ| ≤ m. 
  
  Suppose s(t_0)≥κ for some t_0 ∈ [δ, (δ+1)/2].  Then there exists an integer k such that t' = δ + kΔ∈ [δ, (δ+1)/2] and s(t')≥κ/2, where Δ = κ/(2mn^2).
  
  
  
  
  
    Let k be an integer such that t' := δ + kΔ∈ [δ, (δ+1)/2] and |t'-t_0| ≤Δ.  Since |t_0| ≤ 1 and |t'| ≤ 1, for each ℓ∈{1, … n} we have that
    
      |t'^ℓ - t_0^ℓ|
          ≤  |t' - t_0| ·∑_i=0^ℓ-1| t'^i t_0^ℓ-1-i|
          ≤Δℓ≤Δ n .
  
    
    
    Since |s_ℓ| ≤ m and Δ = κ/(2mn^2), we have 
    
      |s_ℓ t'^ℓ - s_ℓ t_0^ℓ| = |s_ℓ|· |t'^ℓ - t_0^ℓ| ≤ mn Δ = κ/(2n) .
  
    Therefore
    
      s(t') - s(t_0)≤∑_ℓ=1^n s_ℓ t'^ℓ - s_ℓ t_0^ℓ≤κ/2 .
  
    It follows from the triangle inequality that s(t')≥s(t_0) - s(t') - s(t_0)≥κ/2.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   
   
   
  
  
  
  
  
  
  
  
  
  Just to save us from having to look up this trivial argument, here is a fragment that was written about this granularity stuff a while ago, basically just cut and pasted from the old file subword-counts2.tex: 
  
  
  
  
  
  
  Input: w ∈^k, traces y ∼_δ(x)
  
  Output: #(w,x)
  
  High-level algorithm:
  
      
    * Compute estimate _x,w(τ) for τ∈ S := {δ, δ + (n / 1-δ)^-O(k/(1-δ)), ⋯, (δ+1)/2} up to accuracy (n / (1-δ))^-O(k/(1-δ)).
      
    * Get solution q_0 to feasibility LP.
      
    * Round q_0 to the nearest integer and return that.
  
  
  LP:
  
  Variables: q_0, q_1, ⋯ q_n-k∈ [0, n^k] // coefficients of polynomial
  
  Constraints: For all ζ∈ S,
  
      |∑_ℓ q_ℓ ζ^ℓ - _x,k(ζ)| ≤(n/1-δ)^-O(k/(1-δ)).
  
  
  Correctness:
  
  0) W.h.p, we have |_x,k(ζ) - _x,k(ζ)| ≤(n/(1-δ))^-O(k/(1-δ)) simultaneously for all ζ∈ S.
  
  1) Setting q_ℓ to be (_x,w)_ℓ, the degree-ℓ coefficient of the true polynomial _w,x, we see that the constraints are satisfied.  Thus the output returned after rounding would be #(w,x).
  
  2) Let q(ζ) = ∑_ℓ q_ℓ ζ^ℓ be any feasible solution to the above LP. If |q_0 - #(w,x)| ≥ 1/2, then <Ref> (rather, its discretized version) implies that some constraint (corresponding to some ζ∈ S) must be violated. Hence we have a contradiction. Thus any feasible solution must satisfy |q_0 - #(w,x)| < 1/2, and so we must get the correct output #(w,x) after rounding.
  
  
  We now analyze the complexity of the algorithm. Note that for all ζ∈ S, we have 1-ζ≥ (1-δ)/2. 
    By <Ref>, 
  the sample complexity is 
  
      n^O(1)·(2/1-δ)^O(k)·(5/κ)^2 ·log(|S|/τ) 
      = (n^1/(1-δ)/1-δ)^O(k)log(1/τ).
  
  
  
  The running time of the algorithm is (<ref>) multiplied by |S|
    plus the time needed to solve the linear program.
  The former can still be bounded by the same expression on the RHS of
   (<ref>) above.
  The latter can be bounded by (n) multiplied by the number of bits 
    needed to describe the linear program, which can also be bounded by the RHS
    of (<ref>).
  
  
  This proves the claimed upper bounds on the running time and sample complexity, and concludes the proof of <Ref> assuming <Ref>.
  
  
  
  
   §.§ Proof of <Ref>
   
  
  
  In this subsection we prove <Ref>. For convenience we define ρ := 1-δ∈ (0,1), and we restate the theorem below in terms of ρ: 
  
  
  
  
  Restatement of <Ref>: 
  
  Let 1 ≤ n ≤ m.  Let p(z) = ∑_i=0^n p_ℓ z^i be a polynomial of degree at most n with real coefficients such that |p_0| ≥ 1/3, and |p_ℓ|≤ m for all i. Then for any δ∈ (0,1), 
  
      sup_ζ∈ [δ,(δ+1)/2] |p(ζ)| ≥ m^-O(1/(1-δ)).
  
  
  
  
  
  
  Restatement of <Ref>: 
  
  Let 1 ≤ n ≤ m.  Let p(z) = ∑_i=0^n p_i z^i be a polynomial of degree at most n with real coefficients such that |p_0| ≥ 1/2, and |p_i|≤ m for all i. Then for any ρ∈ (0,1), 
  
      sup_ζ∈[1-ρ,1- ρ/2]|p(ζ)| ≥ m^-O(1/ρ).
  
  
  
  The proof uses the Hadamard three-circle theorem, along with other standard results in complex analysis. Consider the mapping w : → given by
  
      w(z) = 1-3ρ/4 + ρ/8(z + 1/z).
  
  We observe that the map w(z) is meromorphic with only one pole 
  at z=0. 
  Define radii
  
      r_1=1 ;   r_2=2;   r_3=4.
  
  For i  = 1,2,3, let C_i ⊂ be the circle centered at the origin with radius r_i. 
  Consider the map f : → given by f(z) = p(w(z)). Like w(·), f is meromorphic with only one pole at z=0. 
  The idea of the proof is to use the Hadamard three-circle theorem <cit.> on f, which tells us that
  
      2 log(sup_z ∈ C_2 |f(z)|) ≤log(sup_z ∈ C_1 |f(z)|) + log(sup_z ∈ C_3 |f(z)|).
  
  
  Now, we will analyze each term in the above inequality. We first record some facts about the behaviour of w over each circle C_i that are immediate from the definition:
  
   
  Let w, C_1,C_2 and C_3 be as defined above.
      
      
    * When z ranges over C_1, w(z) ranges over the real line segment 
      [1-ρ, 1-ρ/2].
    
      
    * When z ranges over C_2, w(z) ranges over the ellipse E_2 in the complex plane which is centered at the real value 1-3ρ/4 and is the locus of all points z=x+iy satisfying
      
      (x - (1-3ρ/4)/5ρ/16)^2 + (y/3ρ/16)^2=1.
  
     
     
    * Similarly, when z ∈ C_3, w(z) ranges over the ellipse E_3 in the complex plane which is centered at the real value 1-3ρ/4 and is the locus of all points z=x+iy satisfying
      
      (x - (1-3ρ/4)/17 ρ / 32)^2 + (y/15ρ/32)^2=1.
  
      Moreover, the ellipse E_3 is completely contained in the unit disk B_1(0).
  
  
  
  
  
   
      
    * When z ranges over C_1, w(z) ranges over the line segment 
      [1-ρ, 1-ρ/2], which is our domain of interest.
    
      
    * When z ranges over C_2, w(z) ranges over the ellipse E_2 which is centered at (1-3ρ/4,0) and is the locus of all points z=x+iy satisfying
      
      (x - (1-3ρ/4)/5ρ/16)^2 + (y/3ρ/16)^2=1.
  
     
     
    * Similarly, when z ∈ C_3, w(z) ranges over the ellipse E_3 which is centered at (1-3ρ/4,0) and is the locus of all points z=x+iy satisfying
      
      (x - (1-3ρ/4)/17 ρ / 32)^2 + (y/15ρ/32)^2=1.
  
  We note that for 0< ρ < 1, the ellipse E_3 is completely contained in the unit circle. 
  
  
  
  
  
  Now, consider the map f : → given by f(z) = p(w(z)). Like w(·), this map f is holomorphic except at z=0. 
  The idea of the proof is to use the Hadamard three-circle theorem on f, which tells us that
  
      2 logsup_z ∈ C_2 |f(z)| ≤logsup_z ∈ C_1 |f(z)| + logsup_z ∈ C_3 |f(z)|.
  
  
  
  <Ref> will be useful to us because of the following simple claim, which is immediate from <Ref>, Item (1):
   
  
      sup_z ∈ C_1 |f(z)| = sup_ζ∈ [1-ρ,1-ρ/2] |p(ζ)|.
  
  
  
  
  <Ref>, item 1 above implies that 
  
      sup_z ∈ C_1 |f(z)| = sup_ζ∈ [1-5ρ/8,1-3 ρ/8] |p(ζ)|.
  
  The claim is now immediate. 
  
  
  
  Given <Ref> and <Ref>, in order to lower bound sup_ζ∈ [1-ρ,1-ρ/2]|p(ζ)|, it suffices to upper bound sup_z ∈ C_3 |f(z)| and to lower bound sup_z ∈ C_2 |f(z)|. We do this in the following claims:
  
   
  
      sup_z ∈ C_3 |f(z)| ≤ m · (n + 1).
  
   
  
    By <Ref>, Item (3) above, we have E_3 ⊆ B_1(0) and so 
    
    
    
      sup_z ∈ C_3 |f(z)| = sup_z ∈ E_3 |p(z)| ≤sup_z ∈ B_1(0) |p(z)|,
  
  
  
  
  The bounds on the coefficients of p immediately imply that sup_z ∈ B_1(0) |p(z)| ≤ m · (n + 1).
  
  
   
  
      sup_z ∈ C_2 |f(z)| ≥ m^-O(1/ρ).
  
  
  
  
  Applying Jensen's formula <cit.> to p on the closed origin-centered disk of radius 1 - 3ρ/4,
  
  
  
  we get that 
  
      𝐄_ [ln |p()|] ≥ln |p(0)| ≥ln (1/2) = - ln 2.
  
  Here  is taken to be a uniform random point on the circle C 
  
  of radius 1-3ρ/4 centered at the origin.
  
  Now, consider the arc 
      = {z ∈ : |z| = 1-3ρ/4  and  |(z)| ≤ 3ρ/16}.
  
  Let c_max, 𝒜 = max_z ∈ |p(z)| and θ^∗ = 3ρ/16 (note that θ^∗/π  is the fraction of C that lies in A). 
  Now since |p(z)| ≤ m(n+1) for all z ∈ B_1-3ρ/4(0) ∖𝒜 (because of the coefficient bound on p), we have by <Ref> that
  
  
  
      (1 - θ^∗/π)ln(m(n+1)) + ln c_max, 𝒜·θ^∗/π≥ 0,   and hence  ln(m(n+1)) + ln c_max, 𝒜·θ^∗/π≥ 0.
  
  
  
  
      -ln 2 ≤(1 - θ^∗/π)ln(m(n+1)) + θ^∗/π·ln c_max, 𝒜≤ln(m(n+1)) + θ^∗/π·ln c_max, 𝒜.
  
  Thus, 
  
      ln c_max, 𝒜≥  -π·ln(2m(n+1))/θ^∗,
  
  and hence
  
      c_max,𝒜≥(2m(n+1))^-π/θ^∗.
  
  
  Next, we observe that the arc  is entirely in the interior of the ellipse E_2. (To see this, observe that the center of the arc is the real value 1-3ρ/4, which coincides with the center of the ellipse, and that every point on the arc is within distance less than 3ρ/16 from the center of the arc (ellipse).  Since 3ρ/16 is the length of the semi-minor axis of the ellipse, it follows that every point in the arc is within the ellipse.)
  We further recall that m ≥ n and that θ^∗ = Θ(ρ). Using these facts along with the maximum modulus principle and <Ref> Item (2), we conclude that 
  
      sup_z ∈ C_2 |f(z)| = sup_z ∈ E_2 |p(z)| ≥sup_z ∈𝒜 |p(z)| = c_max, ≥ m^-O(1/ρ),
  
  and <Ref> is proved.
  
  
      max_z ∈ E_2 |p(z)|  ≥max_z ∈𝒜 |p(z)| = c_max,𝒜.
  
  Observe that 
  
      max_z ∈ E_2 |p(z)| = max_z ∈ C_2 |f(z)|.
  
  This implies the claim (recalling that m ≥ n).
  
  
  
  <Ref> We combine <Ref> in <Ref> to get that
  
      logsup_ζ∈ [1-ρ,1-ρ/2] |p(ζ)| = logsup_z ∈ C_1 |f(z)| ≥ -O(1/ρ) log m - log (m(n+1)) ≥ -O(1/ρ) log m.
  
  Exponentiating both sides finishes the proof of <Ref>.
  
  
  
  
  
  
  
  
  
  § IMPROVED ALGORITHMS: PROOF OF <REF>
   
  
  In this section we give improved algorithms strengthening the quantitative bounds given in <Ref> and <Ref> 
  and thereby complete the proof of <Ref>.
  
  First we describe the main ideas underlying the improved algorithms. Both algorithms benefit from the same insights, so we will just describe the improvement of <Ref> in this overview. 
  
  
  Recall the definition of the subword polynomial _x,w from <Ref>:
  
      _x,w(ζ) := ∑_α∈_≥ 0^k-1
       |α| ≤ n-k #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 … w_k-2∗^α_k-1 w_k-1, x) ·ζ^|α|.
  
  
  
      _x,w(ζ) := ∑_ℓ = 0^n-k( ∑_α∈_≥ 0^k-1, |α| = ℓ#(w_0 ∗^α_1 w_1 ∗^α_2 w_2 … w_k-2∗^α_k-1 w_k-1, x))  ζ^ℓ.
  
  
  
  Grouping terms of the same degree together, we can write it as _x,w(ζ) = ∑_ℓ≥ 0γ_ℓ ζ^ℓ, where
  
      γ_ℓ = ∑_α∈_≥ 0^k-1
       |α| = ℓ#(w_0 ∗^α_1 w_1 ∗^α_2 w_2 … w_k-2∗^α_k-1 w_k-1, x)
  
  is the degree-ℓ coefficient, for each 0 ≤ℓ≤ n-k. 
  
  In the proofs of Corollary <ref> in <Ref> and <Ref> in <Ref>, we bounded these coefficients uniformly by m=n^k. The first insight is that in fact a sharper bound holds for these coefficients: specifically, we have
  
      0 ≤γ_ℓ≤ m_ℓ:=n ℓ + k-2k-2.
  
  This is simply because there are at most n choices for the position of the first character w_0 in x, and there are   ℓ + k-2k-2 
  ways to choose a tuple of non-negative integers α_1, ⋯, α_k-1 that sum to ℓ.  The second insight is that since our approaches only involve evaluating _x,w(ζ) on non-negative real inputs ζ that are bounded below 1, we can exploit this improved coefficient bound to truncate the high-degree portion of the polynomial; working with the resulting (much) lower-degree polynomial leads to an overall gain in efficiency.  
  
  To explain this in more detail, we need the following definition:
  
      Let p(ζ) = ∑_ℓ=0^n p_ℓ ζ^ℓ be a univariate polynomial of degree at most n. For d ∈{0,1,⋯,n}, we define the d-low-degree part of p (denoted as p^≤ d) to be
      
      p^≤ d(ζ) = ∑_ℓ = 0^d p_ℓ ζ^ℓ.
  
      Analogously, we define the d-high-degree part of p to be p^>d(ζ) := ∑_ℓ >d p_ℓ ζ^ℓ = p(ζ) - p^≤ d(ζ).
  
  
  Consider any polynomial q with a constant term which is an integer different from _x,w(0). In order for q to be a polynomial that could possibly arise from the k-subword deck of some string z ∈^n, it must also have coefficients bounded by the right hand side of <Ref>. Using these sharper bounds on  the coefficients, 
  we show that there exists a threshold degree d that is roughly[We ignore the
    dependence on δ for the overview here; see (<ref>) and (<ref>) for exact choices of d.] 
    O( k+log n) such that
    
  
  
  
  
      
    * The d-low-degree part of the polynomials _x,w and q 
      must differ by at least 
      
      
      (1/n(1-δ/2)^k)^O(1/(1-δ))
  
      (see <Ref>) at some point in the interval [δ,(δ+1)/2]. This result is stronger than the analogous ≈ n^-O(k/(1-δ)) lower bound established in <Ref>, which leads to savings on both time and sample complexity. 
      
    * The maximum value that the high-degree part of such polynomials attains on the relevant interval is negligible compared to the difference specified above.
  
  Combining these two facts enables us to carry out our analysis just on the d-low-degree part, which has much smaller coefficients and thereby admits a more efficient algorithm.
  
  In <Ref>, we implement these ideas to strengthen <Ref> when δ < 1/2. In <Ref>, we do the same to derive a stronger analogue of <Ref>, which reduces the sample complexity of computing #(w,x) for general δ < 1 significantly. Finally in <Ref>, we obtain an LP-based algorithm to compute #(w,x) which is faster than the corresponding algorithm in <Ref>.
  
  
  we have
  
      γ_ℓ≤ n ℓ + k-2k-2.
  
  To see this, note that there are at most n choices for the position of the first character w_0 in x, and there are at most ℓ + k-2k-2 choices for non-negative integers α_1, ⋯, α_k-1 with sum ℓ.
  
  
  
  
   §.§ Improvement of <Ref> for deletion rate δ < 1/2
   
  
  
  
  
  
  
  
  
  In this subsection we strengthen <Ref> for deletion rate δ < 1/2 as follows:
  
   
  Let 0 < δ < 1/2. 
  
  There is an algorithm Multiplicity_small-δ which takes as input a string w ∈^k, 
  access to independent traces of an unknown source string x ∈^n, and a parameter τ>0.
  Multiplicity_small-δ draws (n) · (1/2-δ)^-O(k)·log (1/τ) traces from _δ(x), runs in time (n) · (1/2-δ)^-O(k)·log (1/τ), and has the following property: For any unknown source string x ∈^n, with probability at least 1-τ the output of Multiplicity_small-δ is the multiplicity of w in (x,k) (i.e. the number of occurrences of w as a subword of x).
  
  
  
      Recall <Ref>, which relates the subword polynomial value at any point ζ∈ to traces drawn from the deletion channel using Taylor series:
      
      _x,w(ζ) = 1/(1-δ)^k ∑_α∈_≥ 0^k-1
       |α| ≤ n-k _∼_δ(x)[ #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1,) ]·( ζ-δ/1-δ)^|α|.
  
  
  As in <Ref>, our goal is to evaluate _x,w(0) = #(w,x) up to error 1/3 in magnitude, and return the integer nearest to our estimate. Let ξ = (ζ - δ) / (1-δ), so that ζ = δ + ξ (1-δ). 
  
  
  
  Consider the polynomial p defined as follows:
  
      p(ξ) := (1-δ)^k ·_x,w(δ + ξ (1-δ)).
  
  
  
  
  
  
  
  
  We have that _x,w(0) = (1-δ)^-k  p(-δ/(1-δ)), so estimating _x,w(0) up to error ± 1/3 is equivalent to estimating p(-δ/(1-δ)) up to error ± (1-δ)^k/3. As 0 < δ < 1/2, we have 1-δ > 1/2, and so it suffices to estimate p(-δ/(1-δ)) up to error 2^-k/3. Moreover, we have |-δ/(1-δ)| = δ/(1-δ) < 1. We will use these observations to bound the contribution of the high-degree-part of p. Let θ = 1/2 - δ, so that
    δ/(1-δ)≤ 2δ=1-2θ.
  
  
  
  
  
   
      Let δ < 1/2, and let p and θ  
      be as above. Then by setting 
      
      d := C/θ(k lnC/θ + ln n)
  
      with C=e^2, we have  
      
      sup_|ξ| ≤ 1-2θ |p^>d(ξ)| ≤0.1/2^k.
  
  
  
  Before proving <Ref>, we show that it implies <Ref>.
  
   Consider p^≤ d, the d-low-degree-part of p, where d is as given by <Ref>. For all ξ with |ξ| ≤ 1-2θ,
  
      |p(ξ) - p^≤ d(ξ)| = |p^>d(ξ)| ≤0.1/2^k.
  
  So, by the triangle inequality, in order to estimate p(-δ/(1-δ)) up to error ± 2^-k/3, it suffices to estimate p^≤ d(-δ/(1-δ)) up to error ± 2^-k/5. 
  
  
  Let S_d be the set {α∈_≥ 0^k-1: |α| ≤ d}.
  As in <Ref>, let
  
      E_α:=_∼_δ(x)[ #(w_0 ∗^α_1 w_1 ∗^α_2 w_2 ⋯ w_k-2∗^α_k-1 w_k-1,)]
  
  for each α∈ S_d. (Note that by definition, p^≤ d only includes terms E_α for |α| ≤ d.) Then
  
      p^≤ d(ξ)
        = ∑_α∈ S_d E_α·ξ^|α|.
  
  Each E_α is between 0 and n and 
    using the same argument as that following <Ref>, we have  
  
  
  
  
      |S_d|= M:= ∑_ℓ=0^d ℓ + k - 2k-2 = d+k-1k-1≤d+kk
  
  and we use the following claim to bound the right hand side:
  
  
    Let d = C/θ (klnC/θ + ln n) for some θ∈ (0,1] and C ≥ e^2.  Then we have
    
      d+kk≤ n·(C/θ)^3k.
  
  
  
  Using d≥ k and the approximation k!≥√(2π k) (k/e)^k≥ (k/e)^k, we have 
  
      d+kk≤(2d)^k/(k/e)^k=
      exp(kln2ed/k)
         ≤exp(k(2+lnC/θ+ln(lnC/θ+ln n/k))) 
         ≤exp(k(2+lnC/θ+ lnC/θ+ln n/k) )
         ≤ n·(C/θ)^3k,
  
  where (<ref>) used ln a≤ a, (<ref>) used 2 < ln (C/θ) since C ≥ e^2.
    
  
  Plugging  in <Ref>, we have M≤ n /θ^O(k) using θ<1/2.
  
  
  
  
  
  
  
  
  
  
  
  The algorithm just draws s (to be specified)
  traces ∼_δ(x), computes an empirical estimate Ẽ_̃α̃ of E_α for each α∈ S_d so that 
  
      |Ẽ_̃α̃ - E_α| ≤0.2/2^kM.
  
  with probability at least 1-τ.
  This can be achieved by setting the number of traces to be
  
      s := O( (M^2 2^k )^2) ·log( M/τ)= (n/θ^k)^O(1)·log1/τ
  
  and a simple application of a Chernoff bound and a union bound. 
  When this happens, 
  
  
  it follows from the fact that |-δ / (1-δ)| < 1
    that 
      ∑_α∈ S_dẼ_̃α̃·(-δ/1-δ)^|α|
  
    is an estimate that deviates by at most 2^-k/5.
  
  Combined with the observations at the beginning of the proof, this implies that we can estimate _x,w(0) = #(w,x) up to error ± 1/3, and hence our output (the nearest integer to our estimate of _x,w(0)) is #(w,x) with probability at least 1-τ.
  
  The runtime is governed by the time required to compute estimates Ẽ_̃α̃. We can bound it by
  
      s · n^O(1)· |S_d| ≤(n/θ^k)^O(1)·log1/τ = n^O(1)·(1/1/2-δ)^O(k)·log1/τ.
  
  This finishes the proof of the theorem.
  
  
  
  We are interested in |p^>d(ξ)| over |ξ|≤ 1-2θ, which is trivially bounded by
  
      |p^>d(ξ)|
        ≤∑_ℓ=d+1^n-k n ℓ+k-2k-2· (1-2θ)^ℓ≤∑_ℓ=d^n-k n ℓ+kk· (1-2θ)^ℓ.
  
  
  First, we show that terms in the sum on the right hand side above decreases with ℓ so it 
    suffices to bound the term with ℓ=d multiplied by n. 
  
      To see this, observe that
      
      |ℓ+kk/ℓ+k-1k· (1-2θ) | =
              ℓ+k/ℓ· (1-2θ) ≤
              
              1 + k /ℓ - 2θ < 1,
  
      whenever ℓ > k /2 θ, which holds for all ℓ > d given our choice of d. So,
      
      sup_|ξ| ≤ 1-2θ|p^>d(ξ)|
              
              ≤ n^2 d+kk(1 - 2θ)^d
              ≤ n^2 d+kk e^-2θ d.
  
      We have e^-2θ d = n^-2C/θ· (C/θ)^-2Ck/θ, and so plugging in <Ref> we have
      
      n^2 ·(n ·(C/θ)^3k) · e^-2θ d≤ n^3 -2C/θ·( C/θ)^(3-2C/θ)k≤1/n 2^k
  
      because 3-2C/θ≤ -1 when C = e^2.  This concludes the proof of the lemma.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Improvement of <Ref> for deletion rate δ < 1
   
  
  Our main technical result is the following, which is a strengthening of <Ref>:
   
      Fix x ∈^n and w ∈^k with k≤ n. Let q(z) = ∑_ℓ=0^n-k q_ℓ  z^ℓ be any polynomial such that 
      |_x,w(0) - q(0)| ≥ 1/2 
      
      and 0 ≤ q_ℓ≤ m_ℓ 
      for all ℓ∈{0,1,⋯,n-k}. 
      Then 
      
      sup_ζ∈ [δ,(δ+1)/2]|_x,w(ζ) - q(ζ) |≥(1/n(1-δ/2)^k)^O(1/(1-δ)),
                for any δ∈ (0,1).
  
  
  
  
  Let p(z)= _x,w(z) - q(z)=∑_ℓ=0^n-kp_ℓ  z^ℓ.
  Let c > 0 be the constant hidden in the exponent of the RHS of <Ref> in <Ref>.
  Let θ = (1-δ)^2/2.
  We will choose the threshold on the degree to be
  
      d := C/θ(k lnC/θ + ln n)
  
  where C=e^2max(1,c).
  
  
  
  For this d, consider the d-low-degree part p^≤ d. This is a polynomial of degree at most d with |p^≤ d(0)| ≥ 1 /2 and the degree-ℓ coefficient is bounded by
  
      |p^≤ d_ℓ| ≤ nℓ+k-2k-2≤ n d + k-2k-2≤ nd+kk
  
  for all ℓ≤ d. We invoke <Ref> on p^≤ d to conclude that
  
      sup_ζ∈ [δ, (δ+1)/2]|p^≤ d(ζ)| ≥(n d+k k )^-c/(1-δ).
  
  
  The following lemma upper bounds the contribution of the high-degree part p^>d of p:
   
      Let p and d be as above. Then
  
      sup_ζ∈ [δ, (δ+1)/2]|p^> d(ζ)| ≤1/n·(n d+k k )^-c/(1-δ).
  
      
  
  
  
  Before proving this lemma, we show that it implies <Ref>.
  
    
  Since p = p^≤ d + p^>d, 
  we use <Ref> and (<ref>) to get 
  
      sup_ζ∈ [δ, (δ+1)/2]|p(ζ)| ≥  0.9·(n d+k k )^-c/(1-δ).
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Plugging in Claim <ref> with our choice of d, we have 
  
  
  
  
  
  
  
  
      sup_ζ∈ [δ, (δ+1)/2]|p(ζ)|
        ≥ 0.9 (n d+k k )^-c/(1-δ)≥(1/n(1-δ/2)^k)^O(1/(1-δ)),
  
  which concludes the proof of <Ref> using <Ref>.
  
  
  
  
  
  
      This proof is similar to that of <Ref>. 
      First we show that the maximum possible contribution to p^>d(ζ),
      when ζ∈ [δ,(δ+1)/2], arises from the degree-d term in p: 
      
      
      |ℓ+kk/ℓ+k-1k·ζ| = 
            ℓ+k/ℓ· |ζ| ≤(1 + k /ℓ)(1 - 1-δ/2) ≤ 1 + k /ℓ - 1-δ/2 < 1
  
      whenever ℓ > 2k /(1-δ), which holds for all ℓ > d. So,
      
      sup_|ζ| ≤ (δ+1)/2|p^>d(ζ)| ≤ 
            
            n^2 d+kk(1 - 1-δ/2)^d
            ≤ n^2d+kk·exp(-(1-δ)d/2).
  
  It suffices to show that 
  
      n^2d+kk·exp(-(1-δ)d/2)≤1/n(n d+k k )^-c/1-δ
  
  or equivalently,  
  
      n^3+2c/1-δ·d+kk^1+c/1-δ·exp(-(1-δ)d/2) ≤ 1.
  
  By our choice of d we have
  
      exp(-(1-δ)d/2)
        ≤ n^-C/1-δ·(C/θ)^-kC/1-δ .
  
  Using <Ref> again, the left hand side of <Ref> is at most
  
      n^3 + 2c/1-δ - C/1-δ·(C/θ)^k(3 + 3c/1-δ - C/1-δ)≤ 1
  
  because 3 + 3c/1-δ - C/1-δ≤ 0 when C = e^2max(1,c).
  
  
  
  
  
  
  
  
  This concludes the proof of the lemma. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ The algorithm of <Ref>
   
  
  
  
  Armed with <Ref> in place of <Ref>, the algorithm  Multiplicity_large-δ giving <Ref> and its analysis are very similar to the algorithm Multiplicity'_large-δ and its analysis given earlier in <Ref>; we only indicate the differences here. 
  
  The algorithm changes in the following ways:
  
  
  
  
    * In Line 1 of the algorithm, we now set κ to be the RHS of <Ref>:
  
      κ :=(1/n(1-δ/2)^k)^O(1/(1-δ)).
  
  
  With this choice of κ, it follows from the proof
    of <Ref> that  the RHS of <Ref> in <Ref>
    can be bounded from above by 0.01κ.
  
    
  
  
    * Later in Line 1, we now set
  
      Δ := 
      κ/2d^2  m_d=
      κ/2d^2 ·  n d + k-2k-2,
   where d is as given in <Ref> 
  (the idea is that now we are using the sharper coefficient bound 
    m_ℓ≤ m_d
  given by <Ref> rather than the cruder n^k bound used earlier).
  
  Using the bounds established in <Ref>, we have
  
      Δ≥(1/n(1-δ/2)^k)^O(1/(1-δ)).
  
   
  
  
    * The coefficient bound on q_0,…,q_n-k in Line 3(a) for the linear program is now 
  q_ℓ∈ [0, m_ℓ] 
  
  for all ℓ∈{0,1,⋯,n-k} rather than q_0,…,q_n-k∈ [0,n^k] as earlier. 
  
  
  
  
  Assumption: There exists an algorithm (<Ref>) to compute _x,w(ζ) for all ζ∈ [δ, 1] up to error ± with probability at least 1-τ using 
  
      n^2/(1-ζ)^2k ^2log1/τ
  
  traces.Leaving it as an explicit assumption till the relevant lemma in <Ref> is completed.
  
  
  With these changes to the algorithm, most of the analysis goes through unchanged. As before, we observe that with probability at least 1-τ, we have
  
      for 
        every ζ∈ S,  |_x,w(ζ) -_x,w(ζ)| ≤κ/5.
  
  We assume this happens henceforth. The solution which sets q_ℓ=(_x,w)_ℓ, the degree-ℓ coefficient of _x,w, for all ℓ, is clearly feasible.
  
  
  Now we show that every feasible solution q_0,⋯,q_n-k to the linear program must satisfy |q_0 - _x,w(0)| < 1/2; this is the only part of the analysis that is somewhat different. Suppose for  a contradiction that q_0,⋯,q_n-k is a feasible solution with |q_0 - _x,w(0)| ≥ 1/2. Let q(ζ) = ∑_ℓ q_ℓ ζ^ℓ  and define the polynomial p = _x,w-q,
  
  
  
  with coefficients p_ℓ. 
  We invoke <Ref> to get that |p(ζ^*)| ≥κ for some ζ^∗∈ [δ, (δ+1)/2]. 
  By <Ref> (and the remark below the choice
    of κ),
  
      |p(ζ) - p^≤ d(ζ)| = |p^>d(ζ)| ≤0.01κ
  
  for all ζ∈ [δ, (δ+1)/2]. 
  As a result, we have |p^≤ d(ζ^*)|≥ 0.99κ.
  Applying <Ref> with s=p^≤ d, n=d, t_0=ζ^*, m = m_d and our choice of Δ, there exists a ζ'∈ S such that 
    |p^≤ d(ζ')|≥ 0.495κ and thus,
    |p(ζ')|≥ |p^≤ d(ζ')| - |p^>d(ζ')|≥0.485κ.
  Hence, recalling that p = _x,w-q, we have
  
      |_x,w(ζ') - q(ζ')| ≥|p(ζ')| - |_x,w(ζ') -_x,w(ζ')| ≥ 0.285κ>κ/5.
  
  As ζ' ∈ S, the solution q violates a constraint of the LP. This concludes the proof of correctness.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Now we analyze the sample complexity of the algorithm. We have
  
      |S| = O(1/Δ) = (n (2/1-δ)^k)^O(1/(1-δ)),
   using the bounds established in <Ref>. Moreover, all points ζ∈ S satisfy 1-ζ≥ (1-δ)/2. So, by <Ref>, the sample complexity is at most
  
      s = n^O(1)/κ^2(2/1-δ)^O(k)log(|S|/τ)
          = (n (2/1-δ)^k)^O(1/(1-δ))log1/τ.
  
  The running time is dominated by the time required to compute ŜŴ_x,w(ζ) for each ζ∈ S.
  The running time for each ζ can be bounded by (<ref>) and the same expression 
     can be used to bound the overall running time given the bound on |S| above.
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  alpha
  
  
  
  
  
  