Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Lower Bounds for Testing Properties of Functions on Hypergrid Domains

Revision #1
Authors: Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Accepted on: 20th March 2013 21:43
Keywords:

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:

### Paper:

TR13-036 | 13th March 2013 18:40

#### Lower Bounds for Testing Properties of Functions on Hypergrid Domains

TR13-036
Authors: Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Publication: 13th March 2013 19:50
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$.