Open Problems:40 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:54:03Z

updated header

71.58.69.223 at 02:39, 18 February 2013

2013-02-18T02:39:07Z

Krzysztof Onak: Created page with "{{Header |title=Testing Monotonicity and the Lipschitz Property |source=bertinoro11 |who=Sofya Raskhodnikova }} Positive answers to the conjectures below would imply better te..."

2012-11-17T03:33:26Z

Created page with "{{Header |title=Testing Monotonicity and the Lipschitz Property |source=bertinoro11 |who=Sofya Raskhodnikova }} Positive answers to the conjectures below would imply better te..."

New page

{{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}}.

← Older revision		Revision as of 02:39, 18 February 2013
Line 15:		Line 15:
	# 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)$.		# 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}}.		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}}.
		+
		+	== Update ==
		+	The conjecture has been resolved (in the positive direction) by Chakrabarty and Seshadhri {{cite\|ChakrabartyS-13}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Sofya Raskhodnikova