TITLE:     Reconstruction from Subsequences

 

SPEAKER:   Prof. Leonard J. Schulman

           Caltech

 

DATE:      2-3PM, Friday, November 1, 2002

 

LOCATION:  Half Dome, 3L

 

HOST:      Gadiel Seroussi

 

-----------------------------------------------------------------------

 

ABSTRACT:

In a "reconstruction problem" for a class of combinatorial objects,
certain "projection" operations on the objects are specified; each
projection discards some information about its argument. The general
problem is whether the collection of all projections of an object, carries
sufficient information to reconstruct it. We investigate the case in which
the objects are sequences, and their projections are their subsequences of
a fixed length k. We show that reconstruction of sequences of length n
requires k to be at least \exp{\Omega(\log^{1/2} n)}. This improves the
previous bound of \lg n.
Joint work with Miroslav Dudik.