  The sum of entropic uncertainties for the measurement of two non-commuting
observables is not always reduced by the amount of entanglement (quantum
memory) between two parties, and in certain cases may be impacted by quantum
correlations beyond entanglement (discord). An optimal lower bound of entropic
uncertainty in the presence of any correlations may be determined by
fine-graining. Here we express the uncertainty relation in a new form where the
maximum possible reduction of uncertainty is shown to be given by the
extractable classical information. We show that the lower bound of uncertainty
matches with that using fine-graining for several examples of two-qubit pure
and mixed entangled states, and also separable states with non-vanishing
discord.
  Using our uncertainty relation we further show that even in the absence of
any quantum correlations between the two parties, the sum of uncertainties may
be reduced with the help of classical correlations.
