All reports by Author Pranjal Awasthi:

__
TR12-076
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Testing Lipschitz Functions on Hypergrid Domains

__
TR12-075
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Limitations of Local Filters of Lipschitz and Monotone Functions

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

A function $f(x_1, ... , x_d)$, where each input is an integer from 1 to $n$ and output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small ... more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

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