  We study the relationship between refined Chern-Simons theory on lens spaces
S^3/Z_p and (q,t)-deformed Yang-Mills theory on the sphere S^2. We derive the
instanton partition function of (q,t)-deformed U(N) Yang-Mills theory and
describe it explicitly as an analytical continuation of the semi-classical
expansion of refined Chern-Simons theory. The derivations are based on a
generalization of the Weyl character formula to Macdonald polynomials. The
expansion is used to formulate q-generalizations of beta-deformed matrix models
for refined Chern-Simons theory, as well as conjectural formulas for the
chi_y-genus of the moduli space of U(N) instantons on the surface O(-p)--->P^1
for all p which enumerate black hole microstates in refined topological string
theory. We study the large N phase structures of the refined gauge theories,
and match them with refined topological string theory on the resolved conifold.
