Materials:

# Rigidity and Tolerance for Perturbed Lattices / Trace reconstruction for the deletion channel

Yuval Peres (Microsoft Research)
Friday, 29 June 2018
15:40
401

Rigidity and Tolerance for Perturbed Lattices

Consider a perturbed lattice {v+Y_v} obtained by adding IID d-dimensional Gaussian variables {Y_v} to the lattice points in Z^d. Suppose that one point, say Y_0, is removed from this perturbed lattice; is it possible for an observer, who sees just  the remaining points, to detect that a point is missing?

In one and two dimensions, the answer is positive: the two point processes (before and after Y_0 is removed)  can be distinguished by counting points in a large ball and averaging over its radius (cf. Sodin-Tsireslon (2004) and Holroyd and Soo (2011) ).    The situation in higher dimensions is more delicate, as this counting approach fails; our solution depends on a game-theoretic idea, in one direction, and on the unpredictable paths constructed by Benjamini, Pemantle and the speaker (1998), in the other.

Trace reconstruction for the deletion channel

In the trace reconstruction problem, an unknown string x of n bits is observed through  the deletion channel, which deletes each bit with some constant probability q, yielding a contracted string.  How many independent outputs (traces) of the deletion channel are needed to reconstruct x with high probability?

The best lower bound known is linear in n.  Until 2016, the best upper bound was exponential in the square root of $n$. In earlier work with F. Nazarov  (STOC 2017), we improved the square root to a cube root using statistics of individual output bits and some inequalities for Littlewood polynomials on the unit circle.  This bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio).  Our main new result:  If the string x  is random, then  a subpolynomial number of traces suffices; the proof relies on comparison to a random walk.

(Joint works with Alex Zhai, FOCS 2017 and with Nina Holden & Robin Pemantle, COLT 2017.)