TY - JOUR

T1 - Limitations of local filters of lipschitz and monotone functions

AU - Awasthi, Pranjal

AU - Jha, Madhav

AU - Molinaro, Marco

AU - Raskhodnikova, Sofya

N1 - Publisher Copyright:
© 2014 ACM.

PY - 2014/12/1

Y1 - 2014/12/1

N2 - We study local filters for two properties of functions of the form f : {0, 1}d → 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. It outputs a value F(x) such that (i) the reconstructed function F(x) satisfies the property (in our case, is Lipschitz or monotone) and (ii) if the input function f satisfies the property, then for every point x in the domain (with high constant probability) the reconstructed value F(x) differs from f (x) by at most a. Local filters were introduced by Saks and Seshadhri [2010]. The relaxed definition we study is due to Bhattacharyya et al. [2012], except that we further relax it by allowing additive error. Local filters for Lipschitz and monotone functions have applications to areas such as data privacy. We show that every local filter for Lipschitz or monotone functions runs in time exponential in the dimension d, even when the filter is allowed significant additive error. Prior lower bounds (for local filters with no additive error, that is, with a = 0) applied only to a more restrictive class of filters, for example, nonadaptive filters. To prove our lower bounds, we construct families of hard functions and show that lookups of a local filter on these functions are captured by a combinatorial object that we call a c-connector. Then we present a lower bound on the maximum outdegree of a c-connector and show that it implies the desired bounds on the running time of local filters. Our lower bounds, in particular, imply the same bound on the running time for a class of privacy mechanisms.

AB - We study local filters for two properties of functions of the form f : {0, 1}d → 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. It outputs a value F(x) such that (i) the reconstructed function F(x) satisfies the property (in our case, is Lipschitz or monotone) and (ii) if the input function f satisfies the property, then for every point x in the domain (with high constant probability) the reconstructed value F(x) differs from f (x) by at most a. Local filters were introduced by Saks and Seshadhri [2010]. The relaxed definition we study is due to Bhattacharyya et al. [2012], except that we further relax it by allowing additive error. Local filters for Lipschitz and monotone functions have applications to areas such as data privacy. We show that every local filter for Lipschitz or monotone functions runs in time exponential in the dimension d, even when the filter is allowed significant additive error. Prior lower bounds (for local filters with no additive error, that is, with a = 0) applied only to a more restrictive class of filters, for example, nonadaptive filters. To prove our lower bounds, we construct families of hard functions and show that lookups of a local filter on these functions are captured by a combinatorial object that we call a c-connector. Then we present a lower bound on the maximum outdegree of a c-connector and show that it implies the desired bounds on the running time of local filters. Our lower bounds, in particular, imply the same bound on the running time for a class of privacy mechanisms.

UR - http://www.scopus.com/inward/record.url?scp=84921511330&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84921511330&partnerID=8YFLogxK

U2 - 10.1145/2692372.2692373

DO - 10.1145/2692372.2692373

M3 - Article

AN - SCOPUS:84921511330

SN - 1942-3454

VL - 7

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

IS - 1

M1 - 2

ER -