  We consider the stable matching problem when the preference lists are not
given explicitly but are represented in a succinct way and ask whether the
problem becomes computationally easier and investigate other implications. We
give subquadratic algorithms for finding a stable matching in special cases of
natural succinct representations of the problem, the $d$-attribute, $d$-list,
geometric, and single-peaked models. We also present algorithms for verifying a
stable matching in the same models. We further show that for $d = \omega(\log
n)$ both finding and verifying a stable matching in the $d$-attribute and
$d$-dimensional geometric models requires quadratic time assuming the Strong
Exponential Time Hypothesis. This suggests that these succinct models are not
significantly simpler computationally than the general case for sufficiently
large $d$.
