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\}^n\to[0,1]$, Berman et al. initiate in {{cite|BermanRY-12}} study of 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). | |
− | |||
− | + | - '''Problem 1:''' {{cite|BermanRY-12}} describe an $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 {{cite|BermanRY-12}}; nothing non-trivial is known for higher dimensions). | |
− | '''Note:''' | + | '''Note:''' slides describing the setting and open problems can be found on [http://grigory.us/#lp-testing Grigory's webpage]. |