** Reference:**
* Proceedings of the 33rd annual symposium
on Theory of computing (STOC 2001)*, pages 550-559. ACM, 2001.

** Abstract: **
The notion of *private approximation* was introduced recently by
Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation
of a function *f* is another function *F* that approximates
*f* in the usual sense, but does not yield any information on
*x* other than what can be deduced from *f(x)*. As such,
*F(x)* is useful for private computation of *f(x)* (assuming
that *F* can be computed more efficiently than *f*).

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 information" about *x*, again
permits good approximation.

** Keywords: **
NP-hardness, Approximation, Private computation.

** Availability: **
Paper available as Compressed PostScript
(94 Kbyte).

Shai Halevi's home page.