Problem 40: Testing Monotonicity and the Lipschitz Property

From Open Problems in Sublinear Algorithms
Revision as of 01:54, 7 March 2013 by Krzysztof Onak (talk | contribs) (updated header)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
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].