Approximating the Distance to Monotonicity in High Dimensions

作者：Fattal Shahar; Ron Dana^*

来源：ACM Transactions on Algorithms, 2010, 6(3): 52.

DOI：10.1145/1798596.1798605

• Algorithms
• Theory
• Sublinear approximation algorithms
• property testing
• distance approximation
• monotonicity

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 d, 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 inverted right perpendiculard/kinverted left perpendicular and logarithmic in the size of the range vertical bar R vertical bar (if the range is infinite or just very large, then log vertical bar R vertical bar 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 vertical bar R vertical bar).
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).

• 出版日期2010-6