Title: Parallel Monotonicity Reconstruction
Speaker: Seshadhri Comandur, Princeton University
Date: Wednesday, February 13, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Data sets usually have some structural property that make them useful. An array of points may be sorted, a set of points may be in convex position, a graph may be a tree, etc. These properties are very sensitive to noise, and even a small perturbation of the input would destroy the useful structural property. We investigate the problem of "monotonicity reconstruction" in a parallel setting. We have oracle access to a function f defined on the finite domain [n] ^d. We would like to closely approximate f by a monotone function g. This should be done by a procedure (a filter) that given as input a point x \in n^[d] (constant d) outputs the value of g(x), and runs in time that is highly sublinear in n. We construct such an implementation where the the time and space per query is (log n)^O(1) and the total randomness required is polynomial in (log n). Furthermore the distance of the approximating function g from f is at most a constant multiple of the minimum distance of any monotone function from f. This implementation allows for parallelization: one can initialize many copies of the filter with the same short random seed, and they can autonomously handle queries, while producing outputs that are consistent with the same approximating function g.
Joint work with Michael Saks.