  Since the introduction of the Kolmogorov complexity of binary sequences in
the 1960s, there have been significant advancements in the topic of complexity
measures for randomness assessment, which are of fundamental importance in
theoretical computer science and of practical interest in cryptography. This
survey reviews notable research from the past four decades on the linear,
quadratic and maximum-order complexities of pseudo-random sequences and their
relations with Lempel-Ziv complexity, expansion complexity, 2-adic complexity,
and correlation measures.
