Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexander Shen:

TR08-030 | 16th November 2007
Bruno Durand, Alexander Shen, Andrei Romashchenko

Fixed Point and Aperiodic Tilings

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

TR06-006 | 16th December 2005
Alexander Shen

Multisource algorithmic information theory

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

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

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

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-088 | 29th October 2001
Alexander Shen, Nikolay Vereshchagin

Logical operations and Kolmogorov complexity

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

TR01-087 | 29th October 2001
Bruno Durand, Alexander Shen, Nikolay Vereshchagin

Descriptive complexity of computable sequences

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

TR00-026 | 11th April 2000
Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

Combinatorial Interpretation of Kolmogorov Complexity

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

ISSN 1433-8092 | Imprint