ECCC-Report TR13-036https://eccc.weizmann.ac.il/report/2013/036Comments and Revisions published for TR13-036en-usWed, 20 Mar 2013 21:43:09 +0200
Revision 1
| Lower Bounds for Testing Properties of Functions on Hypergrid Domains |
Eric Blais,
Sofya Raskhodnikova,
Grigory Yaroslavtsev
https://eccc.weizmann.ac.il/report/2013/036#revision1We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.
Our lower bounds also apply to the more restricted setting of functions $ f : [n] \rightarrow \mathbb R$ on the line (i.e., to hypergrids with $ d = 1$), where they give optimal lower bounds for all three properties. The lower bound for testing convexity is the first lower bound for that property, and the lower bound for the Lipschitz property is new for tests with 2-sided error.
We obtain our lower bounds via the connection to communication complexity established by Blais, Brody, and Matulef (2012). Our results are the first to apply this method to functions with non- hypercube domains. A key ingredient in this generalization is the set of Walsh functions, an orthonormal basis of the set of functions $ f : [n]^d \rightarrow \mathbb R$.Wed, 20 Mar 2013 21:43:09 +0200https://eccc.weizmann.ac.il/report/2013/036#revision1
Paper TR13-036
| Lower Bounds for Testing Properties of Functions on Hypergrid Domains |
Eric Blais,
Sofya Raskhodnikova,
Grigory Yaroslavtsev
https://eccc.weizmann.ac.il/report/2013/036We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.
Our lower bounds also apply to the more restricted setting of functions $ f : [n] \rightarrow \mathbb R$ on the line (i.e., to hypergrids with $ d = 1$), where they give optimal lower bounds for all three properties. The lower bound for testing convexity is the first lower bound for that property, and the lower bound for the Lipschitz property is new for tests with 2-sided error.
We obtain our lower bounds via the connection to communication complexity established by Blais, Brody, and Matulef (2012). Our results are the first to apply this method to functions with non- hypercube domains. A key ingredient in this generalization is the set of Walsh functions, an orthonormal basis of the set of functions $ f : [n]^d \rightarrow \mathbb R$.Wed, 13 Mar 2013 19:50:55 +0200https://eccc.weizmann.ac.il/report/2013/036