Rigorous Systems Research Group (RSRG) Seminar

The scenery reconstruction problem (and the closely related trace reconstruction problem) in combinatorial statistics is an embarrassingly simple question that has resisted analysis for some decades now, despite repeated efforts by mathematicians and computer scientists. The challenge is to reconstruct a binary string from readings by a faulty machine that skips some of the bits, with the difficulty stemming from the fact that it is not known which bits were skipped. We will survey what is known and describe a partial solution to a simpler and even more embarrassing problem.