Parallel Monotonicity Reconstruction

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 ∈ 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.

Speaker Details

C. Seshadhri is currently a fifth-year graduate student at Princeton University, working with Prof. Bernard Chazelle. His research interests are algorithms for massive data sets, and specifically, sublinear time algorithms such as property testing and online reconstruction algorithms. He has worked on both combinatorial and geometric problems from this perspective. He has also done work in online learning.

Date:
Speakers:
C. Seshadhr
Affiliation:
csesha@cs.princeton.edu