Local monotonicity reconstruction

Michael Saks, C. Seshadhri

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

We investigate the problem of monotonicity reconstruction, as defined by Ailon et al. (2004) in a localized setting. We have oracle access to a nonnegative real-valued function f defined on the domain [n] = {1,⋯, n} (where d is viewed as a constant). 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 outputs the value of g(x), and runs in time that is polylogarithmic 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 time and space per query is (log n)O(1) and the size of the seed is polynomial in log n and d. Furthermore, with high probability, the ratio of the (Hamming) distance between g and f to the minimum possible Hamming distance between a monotone function and f is bounded above by a function of d (independent of n). This allows for a local implementation: 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.

Original languageEnglish (US)
Pages (from-to)2897-2926
Number of pages30
JournalSIAM Journal on Computing
Volume39
Issue number7
DOIs
StatePublished - 2010

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Local reconstruction
  • Monotonicity
  • Property testing
  • Sublinear algorithms

Fingerprint Dive into the research topics of 'Local monotonicity reconstruction'. Together they form a unique fingerprint.

Cite this