Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-036 | 20th March 2013 21:43

Lower Bounds for Testing Properties of Functions on Hypergrid Domains

RSS-Feed

Abstract:

We 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$.



Changes to previous version:

Added support.


Paper:

TR13-036 | 13th March 2013 18:40

Lower Bounds for Testing Properties of Functions on Hypergrid Domains


Abstract:

We 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$.



ISSN 1433-8092 | Imprint