Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Lipschitz:
TR12-075 | 12th June 2012
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

Limitations of Local Filters of Lipschitz and Monotone Functions

We study local filters for two properties of functions $f:\B^d\to \mathbb{R}$: the Lipschitz property and monotonicity. A local filter with additive error $a$ is a randomized algorithm that is given black-box access to a function $f$ and a query point $x$ in the domain of $f$. Its output is a ... more >>>

ISSN 1433-8092 | Imprint