Cancelled: Yuval Peres: Trace reconstruction for the deletion channel

This event has been cancelled.

Speaker: Yuval Peres, Microsoft Research, Redmond

Date: Wednesday, May 03, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: G575

Event Type:

Room Description:

Host: Costis Daskalakis

Contact: Deborah Goodwin, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:

Reminder Subject: TALK: Special Day and Location - Yuval Peres: Trace reconstruction for the deletion channel

Abstract: 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 recently, the best upper bound was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some complex analysis; 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). If the string $x$ is random and q<1/2, we can show a subpolynomial number of traces suffices by comparison to a biased random walk.

(Joint works with Fedor Nazarov and Alex Zhai).

Research Areas:
None selected

Impact Areas:
None selected

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin Email at Monday, March 27, 2017 at 8:48 AM.