  We develop a general operational framework that formalizes the concept of
conditional uncertainty in a measure-independent fashion. Our formalism is
built upon a mathematical relation which we call conditional majorization. We
define conditional majorization and, for the case of classical memory, we
provide its thorough characterization in terms of monotones, i.e., functions
that preserve the partial order under conditional majorization. We demonstrate
the application of this framework by deriving two types of memory-assisted
uncertainty relations: (1) a monotone-based conditional uncertainty relation,
(2) a universal measure-independent conditional uncertainty relation, both of
which set a lower bound on the minimal uncertainty that Bob has about Alice's
pair of incompatible measurements, conditioned on arbitrary measurement that
Bob makes on his own system. We next compare the obtained relations with their
existing entropic counterparts and find that they are at least independent.
