Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On The Communication Complexity of Finding an (Approximate) Stable
  Marriage   In this paper, we consider the communication complexity of protocols that
compute stable matchings. We work within the context of Gale and Shapley's
original stable marriage problem\cite{GS62}: $n$ men and $n$ women each
privately hold a total and strict ordering on all of the members of the
opposite gender. They wish to collaborate in order to find a stable
matching---a pairing of the men and women such that no unmatched pair mutually
prefer each other to their assigned partners in the matching. We show that any
communication protocol (deterministic, nondeterministic, or randomized) that
correctly ouputs a stable matching requires $\Omega(n^2)$ bits of
communication. Thus, the original algorithm of Gale and Shapley is
communication-optimal up to a logarithmic factor. We then introduce a "divorce
metric" on the set of all matchings, which allows us to consider approximately
stable matchings. We describe an efficient algorithm to compute the "distance
to stability" of a given matching. We then show that even under the relaxed
requirement that a protocol only yield an approximate stable matching, the
$\Omega(n^2)$ communication lower bound still holds.

9
The categories of this paper are: nlin
6
The categories of this paper are: astro-ph
10
The categories of this paper are: q-bio
20
The categories of this paper are: acc-phys
16
The categories of this paper are: stat
33
The categories of this paper are: plasm-ph
19
The categories of this paper are: eess
3
The categories of this paper are: physics
14
The categories of this paper are: math-ph
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
2
The categories of this paper are: math
4
The categories of this paper are: cond-mat
24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
5
The categories of this paper are: gr-qc