This talk will focus on complexity measures that are of interest in
areas such as cryptology and can be obtained (in contrast e.g. to the
Kolmogorov complexity) in an algorithmic manner. Typical examples are
the linear complexity, the linear complexity profile, the -error
linear complexity, and the tree complexity.
The linear complexity is a classical complexity measure for binary sequences in the theory of stream ciphers in cryptology. Whereas the linear complexity can be defined only for an ultimately periodic sequence, namely as the length of the shortest linear feedback shift register that can generate the sequence, the closely related concept of the linear complexity profile makes sense for arbitrary sequences.
A refined complexity notion that arose from the stability theory of
stream ciphers is that of the -error linear complexity, where
is a nonnegative integer. The idea here is to consider all sequences
that differ from a given periodic sequence in at most
positions
within the period and to take the least linear complexity of these
sequences.
The main aim of the talk is to discuss recent results and open problems on the above concepts. A noteworthy recent result is, for instance, the proof of Rueppel's conjecture on the expected value of the linear complexity of random sequences with a fixed period.