Difference between revisions of "Open Problems:70"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(typesetting fixes)
Line 7: Line 7:
 
Extending the usual setting of property testing to functions $f\colon\{1,\dots,n\}^d\to[0,1]$, Berman et al. {{cite|BermanRY-14}} study property testing with regard to $L_p$ distances between functions. Namely, these distances are defined as $\operatorname{dist}_p(f,g) = \frac{\lVert f-g\rVert_p}{\lVert \mathbf{1}\rVert_p}$ (for $p > 0$), so that for instance $\operatorname{dist}_1(f,g) = \frac{\lVert f-g\rVert_1}{n^d}$ (and if the functions are Boolean, we get back the Hamming distance).
 
Extending the usual setting of property testing to functions $f\colon\{1,\dots,n\}^d\to[0,1]$, Berman et al. {{cite|BermanRY-14}} study property testing with regard to $L_p$ distances between functions. Namely, these distances are defined as $\operatorname{dist}_p(f,g) = \frac{\lVert f-g\rVert_p}{\lVert \mathbf{1}\rVert_p}$ (for $p > 0$), so that for instance $\operatorname{dist}_1(f,g) = \frac{\lVert f-g\rVert_1}{n^d}$ (and if the functions are Boolean, we get back the Hamming distance).
  
Let $P$ be a class of functions (e.g. monotone, convex, Lipschitz, etc.) A non-tolerant $L_1$ property tester has to distinguish functions $f$ that have a property $P$ from those that are $\epsilon$-far, i.e. $\inf_{g \in P} dist_1(f,g) \ge \epsilon$.
+
Let $P$ be a class of functions (e.g. monotone, convex, Lipschitz, etc.) A non-tolerant $L_1$ property tester has to distinguish functions $f$ that have a property $P$ from those that are $\epsilon$-far, i.e. $\inf_{g \in P} \operatorname{dist}_1(f,g) \ge \epsilon$.
A tolerant $L_1$ property tester has to distinguish functions $f$ that are $\epsilon_1$-close to a property $P$ ($\inf_{g \in P} dist_1(f,g) \le \epsilon_1$) from those that are $\epsilon_2$-far ($\inf_{g \in P} dist_1(f,g) \ge \epsilon_2$).
+
A tolerant $L_1$ property tester has to distinguish functions $f$ that are $\epsilon_1$-close to a property $P$ ($\inf_{g \in P} \operatorname{dist}_1(f,g) \le \epsilon_1$) from those that are $\epsilon_2$-far ($\inf_{g \in P} \operatorname{dist}_1(f,g) \ge \epsilon_2$).
  
 
* '''Problem 1:''' {{cite|BermanRY-14}} describe a non-tolerant $L_1$-tester for convexity whose query complexity, $O(\frac{1}{\varepsilon^{d/2}}+\frac{1}{\varepsilon})$, grows exponentially with the dimension $d$. Is this exponential dependence necessary, or is there a tester with query complexity $O(\frac{1}{\varepsilon^{o(d)}})$?
 
* '''Problem 1:''' {{cite|BermanRY-14}} describe a non-tolerant $L_1$-tester for convexity whose query complexity, $O(\frac{1}{\varepsilon^{d/2}}+\frac{1}{\varepsilon})$, grows exponentially with the dimension $d$. Is this exponential dependence necessary, or is there a tester with query complexity $O(\frac{1}{\varepsilon^{o(d)}})$?

Revision as of 17:16, 15 January 2016

Suggested by Grigory Yaroslavtsev
Source Baltimore 2016
Short link https://sublinear.info/70

Extending the usual setting of property testing to functions $f\colon\{1,\dots,n\}^d\to[0,1]$, Berman et al. [BermanRY-14] study property testing with regard to $L_p$ distances between functions. Namely, these distances are defined as $\operatorname{dist}_p(f,g) = \frac{\lVert f-g\rVert_p}{\lVert \mathbf{1}\rVert_p}$ (for $p > 0$), so that for instance $\operatorname{dist}_1(f,g) = \frac{\lVert f-g\rVert_1}{n^d}$ (and if the functions are Boolean, we get back the Hamming distance).

Let $P$ be a class of functions (e.g. monotone, convex, Lipschitz, etc.) A non-tolerant $L_1$ property tester has to distinguish functions $f$ that have a property $P$ from those that are $\epsilon$-far, i.e. $\inf_{g \in P} \operatorname{dist}_1(f,g) \ge \epsilon$. A tolerant $L_1$ property tester has to distinguish functions $f$ that are $\epsilon_1$-close to a property $P$ ($\inf_{g \in P} \operatorname{dist}_1(f,g) \le \epsilon_1$) from those that are $\epsilon_2$-far ($\inf_{g \in P} \operatorname{dist}_1(f,g) \ge \epsilon_2$).

  • Problem 1: [BermanRY-14] describe a non-tolerant $L_1$-tester for convexity whose query complexity, $O(\frac{1}{\varepsilon^{d/2}}+\frac{1}{\varepsilon})$, grows exponentially with the dimension $d$. Is this exponential dependence necessary, or is there a tester with query complexity $O(\frac{1}{\varepsilon^{o(d)}})$?
  • Problem 2: Obtain a tolerant $L_1$ tester for monotonicity for $d\geq 3$. (There exist testers, albeit maybe non-optimal, in the case $d=1$ or $d=2$, from [BermanRY-14]; nothing non-trivial is known for higher dimensions.)

Note: Slides describing the setting and open problems can be found on Grigory's webpage. Slides of a longer talk are available here.