Problem 40: Testing Monotonicity and the Lipschitz Property

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)$.

1. 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$.
2. 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

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