All reports by Author Alexander Shen:

__
TR08-030
| 16th November 2007
__

Bruno Durand, Alexander Shen, Andrei Romashchenko#### Fixed Point and Aperiodic Tilings

__
TR06-006
| 16th December 2005
__

Alexander Shen#### Multisource algorithmic information theory

__
TR05-095
| 26th August 2005
__

Noga Alon, Ilan Newman, Alexander Shen, GĂˇbor Tardos, Nikolay Vereshchagin#### Partitioning multi-dimensional sets in a small number of ``uniform'' parts

__
TR04-054
| 5th June 2004
__

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

__
TR01-088
| 29th October 2001
__

Alexander Shen, Nikolay Vereshchagin#### Logical operations and Kolmogorov complexity

__
TR01-087
| 29th October 2001
__

Bruno Durand, Alexander Shen, Nikolay Vereshchagin#### Descriptive complexity of computable sequences

__
TR00-026
| 11th April 2000
__

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin#### Combinatorial Interpretation of Kolmogorov Complexity

Bruno Durand, Alexander Shen, Andrei Romashchenko

An aperiodic tile set was first constructed by R.Berger while

proving the undecidability of the domino problem. It turned out

that aperiodic tile sets appear in many topics ranging from

logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set. The

flexibility of this ...
more >>>

Alexander Shen

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.

more >>>Noga Alon, Ilan Newman, Alexander Shen, GĂˇbor Tardos, Nikolay Vereshchagin

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>

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

Alexander Shen, Nikolay Vereshchagin

We define Kolmogorov complexity of a set of strings as the minimal

Kolmogorov complexity of its element. Consider three logical

operations on sets going back to Kolmogorov

and Kleene:

(A OR B) is the direct sum of A,B,

(A AND B) is the cartesian product of A,B,

more >>>

Bruno Durand, Alexander Shen, Nikolay Vereshchagin

We study different notions of descriptive complexity of

computable sequences. Our main result states that if for almost all

n the Kolmogorov complexity of the n-prefix of an infinite

binary sequence x conditional to n

is less than m then there is a program of length

m^2+O(1) that for ...
more >>>

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

The very first Kolmogorov's paper on algorithmic

information theory was entitled `Three approaches to the

definition of the quantity of information'. These three

approaches were called combinatorial, probabilistic and

algorithmic. Trying to establish formal connections

between combinatorial and algorithmic approaches, we

prove that any ...
more >>>