  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > AUTHORS > MIKHAIL V. VYUGIN:
All reports by Author Mikhail V. Vyugin:

TR04-054 | 5th June 2004
Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

#### Non-reducible descriptions for conditional Kolmogorov complexity

Let a program p on input a output b. We are looking for a
shorter program p' having the same property (p'(a)=b). In
addition, we want p' to be simple conditional to p (this
means that the conditional Kolmogorov complexity K(p'|p) is
negligible). In the present paper, we prove that ... more >>>

TR01-052 | 26th April 2001

#### Non-linear Inequalities between Predictive and Kolmogorov Complexity

Predictive complexity is a generalization of Kolmogorov complexity
which gives a lower bound to ability of any algorithm to predict
elements of a sequence of outcomes. A variety of types of loss
functions makes it interesting to study relations between corresponding
predictive complexities.

Non-linear inequalities between predictive complexity of ... more >>>

TR01-043 | 26th April 2001

#### 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 >>>

TR00-035 | 6th June 2000
Nikolay Vereshchagin, Mikhail V. Vyugin

#### Independent minimum length programs to translate between given strings

A string $p$ is called a program to compute $y$ given $x$
if $U(p,x)=y$, where $U$ denotes universal programming language.
Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$
is defined as minimum length of
a program to compute $y$ given $x$.
Let $K(x)$ denote $K(x|\text{empty string})$
(Kolmogorov complexity of $x$) ... more >>>

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$
as
$$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 >>>

ISSN 1433-8092 | Imprint