# Editing Open Problems:70

**Warning:** You are not logged in. Your IP address will be publicly visible if you make any edits. If you **log in** or **create an account**, your edits will be attributed to your username, along with other benefits.

The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision | Your text | ||

Line 1: | Line 1: | ||

{{Header | {{Header | ||

+ | |title=Open Problems in $L_p$-Testing | ||

|source=baltimore16 | |source=baltimore16 | ||

|who=Grigory Yaroslavtsev | |who=Grigory Yaroslavtsev | ||

}} | }} | ||

+ | |||

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} | + | 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$. |

β | A tolerant $L_1$ property tester has to distinguish functions $f$ that are $\epsilon_1$-close to a property $P$ ($\inf_{g \in P} | + | 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$). |

* '''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)}})$? | ||

Line 12: | Line 14: | ||

* '''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 {{cite|BermanRY-14}}; nothing non-trivial is known for higher dimensions.) | * '''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 {{cite|BermanRY-14}}; nothing non-trivial is known for higher dimensions.) | ||

β | '''Note:''' Slides describing the setting and open problems can be found on [http://grigory.us/#lp-testing Grigory's webpage | + | '''Note:''' Slides describing the setting and open problems can be found on [http://grigory.us/#lp-testing Grigory's webpage]. |