### DIMACS Theoretical Computer Science Seminar

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.