A fundamental problem in science 
is the characterization of objects,

such as sequences, images, networks 
and proteins.

Complexity measures allow scientists 
to do some of these characterizations

in a systematic way to better understand 
and even manipulate these objects.

However, most measures 
are not independent

of the different ways 
in which objects can be described.

A network, for example,

can be described by its adjacency matrix 
or by its degree sequence.

Only universal measures of complexity,

based on the notion 
of a computer program,

can characterize the object -

independent of the way 
in which the network is described.

These universal and powerful measures, 
introduced by mathematicians, exist -

but they are very hard 
to estimate numerically.

The coding theorem method,

based on the work 
of Kolmogorov and Chaitin,

is a method that we've introduced

in order to characterize 
the complexity of an object,

based on these universal 
algorithmic measures.

The idea is,

that if an object can be generated 
by a short computer program,

it is more likely 
to be generated by chance

than an object generated 
by a long computer program.

For example, 
consider the mathematical constant pi.

If you wanted to produce 
the first 1000 digits of pi,

the chances to do so 
by typing them at random are very low -

but the chances to produce 
not the digits,

but a formula that produces any number 
of digits of pi, are much higher -

because pi has many short formulas 
that generate its digits.

What we do then is to run a huge number 
of small computer programs,

in order to count the number of times 
that an output is produced.

From this, we were able to estimate 
how likely an object is to be produced

by a computer program, 
building a distribution.

This distribution helps us 
to characterize objects

and devise applications that could not 
have been conceived before.

The block decomposition method

is a method that extends the power 
of the coding theorem method

to approximate the algorithmic complexity
of larger objects,

such as sequences, images and networks.

This method is based on

Solomonoff and Levin's 
theory of algorithmic probability,

relating the frequency of production of 
an object and its intrinsic properties.

What the block decomposition method does

is to decompose an object 
into smaller pieces,

which we then cleverly stick together
with a formula.

Every one of these pieces is each 
produced by a small computer program,

so we know that the sequence of small 
computer programs

produced the longer piece.

Because the decomposition does not always 
produce pieces of the same type,

there are many ways 
to stick the pieces together -

such as overlapping the pieces,

embedding the original object
in a topological torus,

or assigning similar 
algorithmic complexity

to objects that have similar 
statistical properties.

One of the most interesting properties 
of the block decomposition method

is that it globally calculates
Shannon entropy in the long-range,

but it provides local estimates about 
rhythmic complexity in the short-range.

This hybrid measure of complexity

helps scientists characterize objects 
in more complete ways,

leading to enhanced understanding 
and new discoveries.