Lower bounds for trace reconstruction

In the trace reconstruction problem, an unknown bit string x.{0,1}n is sent through a deletion channel where each bit is deleted independently with some probability q.(0,1), yielding a contracted string x.. How many i.i.d. samples of x. are needed to reconstruct x that at least cn5/4/logn...... traces are required to distinguish between x and y for some absolute constant c, improving the previous lower bound of cn . Furthermore, our result improves the previously known lower bound for reconstruction of random strings from clog2n to clog9/4n/loglogn..........