Raymond Wu, Jie Lu
ITA Conference 2007
The principle of minimum message length (MML) within the theory of algorithmic complexity is discussed. The MML principle is stated as: minqq{-log P(x|y)-log Q(y)}, where Q(y) is a prior probability for hypothesis y, -log Q(y) is the ideal Shannon code length for it, and -log P(x|y) the same for the data x given the hypothesis y. If in the conditional Kolmogorov complexity K(x|y) of a string x, given another string y, the latter string is interpreted as representing a hypothesis, the sum K (x|y)+K (y) could be taken as the shortest code length for the pair x, y by analogy with the MML principle.
Raymond Wu, Jie Lu
ITA Conference 2007
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
M.F. Cowlishaw
IBM Systems Journal
Eric Price, David P. Woodruff
FOCS 2011