# Difference between revisions of "Open Problems:70"

(Created page with "{{Header |title=Open Problems in $L_p$-Testing |source=baltimore16 |who=Grigory Yaroslavtsev }} Extending the usual setting of property testing to functions $f\colon\{1,\dots...") |
|||

Line 5: | Line 5: | ||

}} | }} | ||

− | 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- | + | 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-14}} 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- | + | - '''Problem 1:''' {{cite|BermanRY-14}} 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- | + | - '''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]. |

## Revision as of 21:36, 10 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\}^n\to[0,1]$, Berman et al. initiate in [BermanRY-14] 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:** [BermanRY-14] 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 [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.