All reports by Author Andrej Muchnik:

__
TR04-054
| 5th June 2004
__

Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin#### Non-reducible descriptions for conditional Kolmogorov complexity

__
TR04-015
| 24th February 2004
__

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet#### Enumerations of the Kolmogorov Function

__
TR01-089
| 29th October 2001
__

Andrej Muchnik, Nikolay Vereshchagin#### Logical operations and Kolmogorov complexity. II

__
TR00-015
| 16th February 2000
__

Andrej Muchnik, Alexej Semenov#### Multi-conditional Descriptions and Codes in Kolmogorov Complexity

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

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

A recursive enumerator for a function $h$ is an algorithm $f$ which

enumerates for an input $x$ finitely many elements including $h(x)$.

$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$

is among the first $k(n)$ elements enumerated by $f$.

If there is a $k(n)$-enumerator for ...
more >>>

Andrej Muchnik, Nikolay Vereshchagin

We invistigate what is the minimal length of

a program mapping A to B and at the same time

mapping C to D (where A,B,C,D are binary strings). We prove that

it cannot be expressed

in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C),

..., their ...
more >>>

Andrej Muchnik, Alexej Semenov