Approximating the distance to monotonicity in high dimensions
Shahar Fattal, Dana Ron · ACM Transactions on Algorithms · 2010
In this article we study the problem of approximating the distance of a function f : [ n ] d → R to monotonicity where [ n ] = {1,…, n } and R is some fully ordered range. Namely, we are interested in randomized sublinear algorithms that approximate the Hamming distance between a given function and the closest monotone function. We allow both an additive error, parameterized by δ, and a multiplicative error. Previous work on distance approximation to monotonicity focused on the one-dimensional case and the only explicit extension to higher dimensions was with a multiplicative approximation factor exponential in the dimension d . Building on Goldreich et al. [2000] and Dodis et al. [1999], in which there are better implicit results for the case n =2, we describe a reduction from the case of functions over the d -dimensional hypercube [ n ] d to the case of functions over the k -dimensional hypercube [ n ] k , where 1≤ k ≤ d . The quality of estimation that this reduction provides is linear in ⌈ d / k ⌉ and logarithmic in the size of the range | R | (if the range is infinite or just very large, then log | R | can be replaced by d log n ). Using this reduction and a known distance approximation algorithm for the one-dimensional case, we obtain a distance approximation algorithm for functions over the d -dimensional hypercube, with any range R , which has a multiplicative approximation factor of O ( d log | R |). For the case of a binary range, we present algorithms for distance approximation to monotonicity of functions over one dimension, two dimensions, and the k -dimensional hypercube (for any k ≥ 1). Applying these algorithms and the reduction described before, we obtain a variety of distance approximation algorithms for Boolean functions over the d -dimensional hypercube which suggest a trade-off between quality of estimation and efficiency of computation. In particular, the multiplicative error ranges between O ( d ) and O (1).