# Problem 40: Testing Monotonicity and the Lipschitz Property

From Open Problems in Sublinear Algorithms

Suggested by | Sofya Raskhodnikova |
---|---|

Source | Bertinoro 2011 |

Short link | https://sublinear.info/40 |

Positive answers to the conjectures below would imply better testers for monotonicity and the Lipschitz property. Consider a function $f : \{0,1\}^d \to\mathbb{R}$. It corresponds to a $d$-dimensional hypercube with the vertex set $\{0,1\}^d$ and (directed or undirected, depending on the problem) edges $(x,y)$ for all $x$ and $y$, where $y$ can be obtained from $x$ by increasing one bit. Each node $x$ is labeled by a real number $f(x)$.

- A directed edge $(x,y)$ of the hypercube is
*violated*if $f(x) > f(y)$. Function $f$ is*monotone*if no edges are violated.**Question:**Suppose $v$ edges are violated. Give an upper bound on the number of node labels that have to be changed to make $f$ monotone.**Background:**The best known bound is $vd$ [DodisGLRRS-99] but the conjecture is $v$. - An undirected edge $(x,y)$ of the hypercube is
*violated*if $|f(x) - f(y)| > 1$. Function $f$ is*Lipschitz*if no edges are violated.**Question:**Suppose $v$ edges are violated. Give an upper bound on the number of node labels that have to be changed to make function $f$ Lipschitz in terms of $v$ and $d$.**Background:**Nothing nontrivial is known for real labels. The conjecture is $O(v)$.

For integer labels, the best known bound is $2v \cdot {\rm ImageDiameter}(f)$, where ${\rm ImageDiameter}(f)=\max_x f(x) - \min_x f(x)$ [JhaR-11].

## Update[edit]

The conjecture has been resolved (in the positive direction) by Chakrabarty and Seshadhri [ChakrabartyS-13].