Open Problems:70 - Revision history

Krzysztof Onak: Updating header

2016-01-18T18:41:11Z

Updating header

Krzysztof Onak: Krzysztof Onak moved page Waiting:Grigory to Open Problems:70 without leaving a redirect: Moving to main list of problems

2016-01-18T18:37:34Z

Krzysztof Onak moved page Waiting:Grigory to Open Problems:70 without leaving a redirect: Moving to main list of problems

Krzysztof Onak: typesetting fixes

2016-01-15T17:16:18Z

typesetting fixes

2607:F470:6:400D:75F4:4051:85CF:4152 at 16:52, 15 January 2016

2016-01-15T16:52:44Z

2607:F470:6:400D:75F4:4051:85CF:4152 at 16:48, 15 January 2016

2016-01-15T16:48:52Z

2607:F470:6:400D:75F4:4051:85CF:4152 at 16:48, 15 January 2016

2016-01-15T16:48:08Z

2607:F470:6:400D:75F4:4051:85CF:4152: Added definitions + fixed typos

2016-01-15T16:46:56Z

Added definitions + fixed typos

Krzysztof Onak: Small fixes

2016-01-12T21:37:40Z

Small fixes

Ccanonne at 21:36, 10 January 2016

2016-01-10T21:36:08Z

Ccanonne: 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..."

2016-01-10T21:32:01Z

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..."

New page

{{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,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:''' slides describing the setting and open problems can be found on [http://grigory.us/#lp-testing Grigory's webpage].

@@ 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).
-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)}})$?

← Older revision		Revision as of 16:52, 15 January 2016
Line 14:		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]. Slides of a longer talk are available [http://grigory.us/files/talks/BRY-STOC14.pdf here].

@@ Line 8: / Line 8: @@
 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} dist_1(f,g) \ge \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} 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)}})$?

@@ Line 10: / Line 10: @@
 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) \ge \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 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 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 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].

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

@@ Line 1: / Line 1: @@
 {{Header
 |source=baltimore16
 |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).

← Older revision	Revision as of 18:37, 18 January 2016
(No difference)

@@ 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-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).
+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-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 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-12}}; 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].