Approximating the distance to monotonicity in high dimensions

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 rand...