TY - GEN

T1 - Parallel monotonicity reconstruction

AU - Saks, Michael

AU - Seshadhri, C.

PY - 2008

Y1 - 2008

N2 - We investigate the problem of monotonicity reconstruction, as defined in [3], in a parallel setting. We have oracle access to a nonnegative real-valued function f defined on domain [n] d = {1,..., 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 × ∈ [n] d outputs the value of g(x), and runs in time that is highly sublinear in n. The procedure can (indeed must) be randomized, but we require that all of the randomness be specified in advance by a single short random seed. We construct such an implementation where the the time and space per query is (log n) O(1) and the size of the seed is polynomial in log n and d. 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.

AB - We investigate the problem of monotonicity reconstruction, as defined in [3], in a parallel setting. We have oracle access to a nonnegative real-valued function f defined on domain [n] d = {1,..., 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 × ∈ [n] d outputs the value of g(x), and runs in time that is highly sublinear in n. The procedure can (indeed must) be randomized, but we require that all of the randomness be specified in advance by a single short random seed. We construct such an implementation where the the time and space per query is (log n) O(1) and the size of the seed is polynomial in log n and d. 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.

UR - http://www.scopus.com/inward/record.url?scp=58449110603&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449110603&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449110603

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 962

EP - 971

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -