message is sent through a channel where bits may be deleted or inserted without warning.  How many independent copies of the altered message are required in order to recover the original message? This is harder than the analogous problem in which the bits are erased (but you can see they are gone) or altered (without warning) because of the synchronization problem.  We show that in the average case, exp (c log^{1/3} n) transmissions are required for reconstruction. Previously to this, a sub-polynomial bound was known, but only for small deletion rates and no insertion. The best bound for deletion rates over 1/2 (even without insertion) was superpolynomial: exp(c n^{1/3}) – no log in the exponent.

Joint work with Nina Holden and Yuval Peres.