Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with conditional complexity:
TR00-016 | 29th February 2000
Mikhail V. Vyugin

Information Distance and Conditional Complexities

C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.H.~Zurek
have defined information distance between two strings $x$, $y$
d(x,y)=\max\{ K(x|y), K(y|x) \}
where $K(x|y)$ is the conditional Kolmogorov complexity.
It is easy to see that for any string $x$ and any integer $n$
there is a string $y$ ... more >>>

TR01-043 | 26th April 2001
Mikhail V. Vyugin, Vladimir Vyugin

Predictive complexity and information

A new notion of predictive complexity and corresponding amount of
information are considered.
Predictive complexity is a generalization of Kolmogorov complexity
which bounds the ability of any algorithm to predict elements of
a sequence of outcomes. We consider predictive complexity for a wide class
of bounded loss functions which ... more >>>

ISSN 1433-8092 | Imprint