Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HYPERGRIDS:
Reports tagged with hypergrids:
TR13-036 | 13th March 2013
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

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

Revisions: 1

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

ISSN 1433-8092 | Imprint