• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Limitations of Local Filters of Lipschitz and Monotone Functions
【24h】

Limitations of Local Filters of Lipschitz and Monotone Functions

机译：Lipschitz和单调函数的局部滤波器的局限性

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study local filters for two properties of functions 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. Its output is 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 (SICOMP 2010) and the relaxed definition we study is due to Bhattacharyya et al. (RANDOM 2010), 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, i.e., with a = 0) applied only to more restrictive class of filters, e.g., 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.
机译：我们研究函数f的两个属性的局部滤波器：{0,1}〜d→R：Lipschitz属性和单调性。具有加法误差a的局部滤波器是一种随机算法，可以对函数f和f域中的查询点x进行黑盒访问。它的输出是一个值F（x），因此（i）重构函数F（x）满足属性（在我们的情况下为Lipschitz或单调），并且（ii）如果输入函数f满足属性，则对于域中的每个点x（具有较高的恒定概率），重构值F（x）与f（x）的差异最多为a。 Saks和Seshadhri（SICOMP 2010）引入了局部滤波器，我们研究的宽松定义归功于Bhattacharyya等人。 （RANDOM 2010），除了我们通过允许附加误差进一步放松它。 Lipschitz和单调功能的本地过滤器可应用于数据隐私等领域。我们显示，即使允许滤波器产生明显的加性误差，每个用于Lipschitz或单调函数的局部滤波器也会在时间维度d中以指数形式运行。先前的下限（对于没有加性误差的局部滤波器，即a = 0）仅适用于限制性更强的一类滤波器，例如非自适应滤波器。为了证明我们的下限，我们构造了一系列硬函数，并证明了这些函数上的局部过滤器的查找被称为c连接器的组合对象捕获。然后，我们给出了c连接器的最大出界的下限，并表明它暗示了本地过滤器运行时间的期望界限。对于一类隐私机制，我们的下限尤其意味着运行时间的上限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号