Private approximation of NP-hard functions

Private approximation of NP-hard functions
复制标题

NP-hard 函数的私有逼近

DOI：
--
复制
发表时间：
2001
期刊：
Symposium on the Theory of Computing
影响因子：
--
通讯作者：
Kobbi Nissim
Kobbi Nissim
中科院分区：
--
文献类型：
--
作者：
S. Halevi;Robert Krauthgamer;E. Kushilevitz;Kobbi Nissim

文献摘要

被引文献

相似文献

私人近似&lt；/italic&gt；的概念是最近由Feenerbaum、Fong、Strauss和Wright提出的。非正式地说，函数&lt；italic&gt；f&lt；/italic&gt；的私有近似是另一个函数&lt；italic&gt；f&lt；/italic&gt；，它近似于通常意义上的&lt；italic&>；f&lt；/italic&>；，但除了可以从&lt；italic&>；f(X)&lt；推导出的信息外，它不会产生任何有关&lt；italic&gt；x&lt；/italic&gt；的信息。因此，&lt；italic&gt；F(X)&lt；/italic&gt；对于&lt；italic&gt；f(X)&lt；/italic&gt；的私人计算非常有用(假设&lt；italic&gt；F&lt；/italic&>；的计算效率高于&lt；italic&>；f&lt；/italic&>t；。 在这项工作中，我们研究了这一新概念的特性和局限性。特别地，我们证明了对于许多NP-Hard问题，隐私要求排除了非平凡近似。即使在其他情况下承认非常好的近似性的问题(例如，PTA问题)也是如此。另一方面，我们也表明，略微放松隐私要求，通过泄露“一些关于&lt；italic&gt；x&lt；/italic&>；的信息”，再次允许很好的近似性。
The notion of <italic>private approximation</italic> was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function <italic>f</italic> is another function <italic>F</italic> that approximates <italic>f</italic> in the usual sense, but does not yield any information on <italic>x</italic> other than what can be deduced from <italic>f(x)</italic>. As such, <italic>F(x)</italic> is useful for private computation of <italic>f(x)</italic> (assuming that <italic>F</italic> can be computed more efficiently than <italic>f</italic>. In this work we examine the properties and limitations of this new notion. Specifically, we show that for many NP-hard problems, the privacy requirement precludes non-trivial approximation. This is the case even for problems that otherwise admit very good approximation (e.g., problems with PTAS). On the other hand, we show that slightly relaxing the privacy requirement, by means of leaking “just a few bits of informationrdquo; about <italic>x</italic>, again permits good approximation.