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

__
TR01-052
| 26th April 2001
__

Mikhail V. Vyugin, Vladimir Vyugin#### Non-linear Inequalities between Predictive and Kolmogorov Complexity

__
TR01-043
| 26th April 2001
__

Mikhail V. Vyugin, Vladimir Vyugin#### Predictive complexity and information

__
TR00-035
| 6th June 2000
__

Nikolay Vereshchagin, Mikhail V. Vyugin#### Independent minimum length programs to translate between given strings

__
TR00-016
| 29th February 2000
__

Mikhail V. Vyugin#### Information Distance and Conditional Complexities

Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

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

Mikhail V. Vyugin, Vladimir Vyugin

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

Mikhail V. Vyugin, Vladimir Vyugin

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

Nikolay Vereshchagin, Mikhail V. Vyugin

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

Mikhail V. Vyugin

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