Authors:Rudolf Ahlswede, Levon Khachatrian, C. Mauduit and A. Sárközy
In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were
introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography)
it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if
it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences
constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated.