* Slightly delayed, Feb’s open problem is by one of the three possible “yours truly”s, Sesh. Looking for more reader participation, hint, hint.*

**Basic setting:** Consider \(f:\{0,1\}^n \rightarrow R\), where \(R\) is some ordered range. There is a natural coordinate-wise partial order denoted by \(\prec\). The function is *monotone* if for all \(x \prec y\), \(f(x) \leq f(y)\). The *distance to monotonicity*, \(\epsilon_f\) is the minimum fraction of values that must be changed to make \(f\) monotone. This is an old problem in property testing.

**Open problem:** Is there an efficient constant factor approximation algorithm for \(\epsilon_f\)? In other words, is there a \(poly(n/\epsilon_f)\) time procedure that can output a value \(\epsilon’ = \Theta(\epsilon_f)\)?

**State of the art:** Existing monotonicity testers give an \(O(n)\)-approximation for \(\epsilon_f\), so there is much much room for improvement. (I’d be happy to see a \(O(\log n)\)-approximation.) Basically, it is known that the number of edges of \(\{0,1\}^n\) that violate monotonicity is at least \(\epsilon_f 2^{n-1}\) [GGLRS00], [CS13]. A simple exercise (given below) shows that there are at most \(n\epsilon_f 2^n\) violated edges. So just estimate the number of violated edges for an \(O(n)\)-approximation.

(Consider \(S \subseteq \{0,1\}^n\) such that modifying \(f\) on \(S\) makes it monotone. Every violated edge must have an endpoint in \(S\).)

**Related work:** Fattal and Ron [FR10] is a great place to look at various related problems, especially for hypergrid domains.

**References**

[CS13] D. Chakrabarty and C. Seshadhri. *Optimal Bounds for Monotonicity and Lipschitz Testing over Hypercubes and Hypergrids*. Symposium on Theory of Computing, 2013.

[FR10] S. Fattal and D. Ron.* Approximating the distance to monotonicity in high dimensions *. ACM Transactions on Algorithms, 2010.

[GGL+00] O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky.* Testing Monotonicity *. Combinatorica, 2000.

Pingback: News for November 2019 | Property Testing Review