All reports by Author Madhav Jha:

__
TR14-042
| 2nd April 2014
__

Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri#### Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

__
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

__
TR11-057
| 15th April 2011
__

Madhav Jha, Sofya Raskhodnikova#### Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

Revisions: 2

Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. ... more >>>

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

Madhav Jha, Sofya Raskhodnikova

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>