Harald Niederreiter: Complexity Measures for Binary Sequences

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 $k$-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 $k$-error linear complexity, where $k$ is a nonnegative integer. The idea here is to consider all sequences that differ from a given periodic sequence in at most $k$ 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.

Back to the Index

Please send comments and corrections to Thomas Klausner.