Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximate Privacy: Foundations and Quantification   Increasing use of computers and networks in business, government, recreation,
and almost all aspects of daily life has led to a proliferation of online
sensitive data about individuals and organizations. Consequently, concern about
the privacy of these data has become a top priority, particularly those data
that are created and used in electronic commerce. There have been many
formulations of privacy and, unfortunately, many negative results about the
feasibility of maintaining privacy of sensitive data in realistic networked
environments. We formulate communication-complexity-based definitions, both
worst-case and average-case, of a problem's privacy-approximation ratio. We use
our definitions to investigate the extent to which approximate privacy is
achievable in two standard problems: the second-price Vickrey auction and the
millionaires problem of Yao.
  For both the second-price Vickrey auction and the millionaires problem, we
show that not only is perfect privacy impossible or infeasibly costly to
achieve, but even close approximations of perfect privacy suffer from the same
lower bounds. By contrast, we show that, if the values of the parties are drawn
uniformly at random from {0,...,2^k-1}, then, for both problems, simple and
natural communication protocols have privacy-approximation ratios that are
linear in k (i.e., logarithmic in the size of the space of possible inputs). We
conjecture that this improved privacy-approximation ratio is achievable for any
probability distribution.

33
The categories of this paper are: plasm-ph
35
The categories of this paper are: mtrl-th
15
The categories of this paper are: nucl-ex
25
The categories of this paper are: patt-sol
18
The categories of this paper are: econ
8
The categories of this paper are: hep-ex
17
The categories of this paper are: q-fin
12
The categories of this paper are: nucl-th
2
The categories of this paper are: math
21
The categories of this paper are: adap-org
14
The categories of this paper are: math-ph
32
The categories of this paper are: atom-ph
10
The categories of this paper are: q-bio
22
The categories of this paper are: chao-dyn
26
The categories of this paper are: bayes-an
7
The categories of this paper are: hep-th