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