  We examine the problem of counting bound states of BPS black holes on local
Calabi-Yau threefolds which are fibrations over a Riemann surface by computing
the partition function of q-deformed Yang-Mills theory on the Riemann surface.
We study in detail the genus zero case and obtain, at finite $N$, the instanton
expansion of the gauge theory. It can be written exactly as the partition
function for U(N) Chern-Simons gauge theory on a Lens space, summed over all
non-trivial vacua, plus a tower of non-perturbative instanton contributions.
The correspondence between two and three dimensional gauge theories is
elucidated by an explicit mapping between two-dimensional Yang-Mills instantons
and flat connections on the Lens space. In the large $N$ limit we find a
peculiar phase structure in the model. At weak string coupling the theory
reduces exactly to the trivial flat connection sector with instanton
contributions exponentially suppressed, and the topological string partition
function on the resolved conifold is reproduced in this regime. At a certain
critical point all non-trivial vacua contribute, instantons are enhanced and
the theory appears to undergo a phase transition into a strong coupling regime.
We rederive these results by performing a saddle-point approximation to the
exact partition function. We obtain a q-deformed version of the Douglas-Kazakov
equation for two-dimensional Yang-Mills theory on the sphere, whose one-cut
solution below the transition point reproduces the resolved conifold geometry.
Above the critical point we propose a two-cut solution that should reproduce
the chiral-antichiral dynamics found for black holes on the Calabi-Yau
threefold and the Gross-Taylor string in the undeformed limit.
