Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MADHAV JHA:
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

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


TR12-076 | 12th June 2012
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

Testing Lipschitz Functions on Hypergrid Domains

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


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


TR11-057 | 15th April 2011
Madhav Jha, Sofya Raskhodnikova

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

Revisions: 2

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




ISSN 1433-8092 | Imprint