  The distillable randomness of a bipartite quantum state is an
information-theoretic quantity equal to the largest net rate at which shared
randomness can be distilled from the state by means of local operations and
classical communication. This quantity has been widely used as a measure of
classical correlations, and one version of it is equal to the regularized
Holevo information of the ensemble that results from measuring one share of the
state. However, due to the regularization, the distillable randomness is
difficult to compute in general. To address this problem, we define measures of
classical correlations and prove a number of their properties, most importantly
that they serve as upper bounds on the distillable randomness of an arbitrary
bipartite state. We then further bound these measures from above by some that
are efficiently computable by means of semi-definite programming, we evaluate
one of them for the example of an isotropic state, and we remark on the
relation to quantities previously proposed in the literature.
