Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Lipschitzness:
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