Editing Open Problems:40

{{Header
|title=Testing Monotonicity and the Lipschitz Property
|source=bertinoro11
|who=Sofya Raskhodnikova
}}
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.<br>'''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.<br>'''Background:''' The best known bound is $vd$ {{cite|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.<br>'''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$.<br>'''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)$ {{cite|JhaR-11}}.