  Both the Thue-Morse and Rudin-Shapiro sequences are not suitable sequences
for cryptography since their expansion complexity is small and their
correlation measure of order 2 is large. These facts imply that these sequences
are highly predictable despite the fact that they have a large maximum order
complexity. Sun and Winterhof (2019) showed that the Thue-Morse sequence along
squares keeps a large maximum order complexity. Since, by Christol's theorem,
the expansion complexity of this rarefied sequence is no longer bounded, this
provides a potentially better candidate for cryptographic applications. Similar
results are known for the Rudin-Shapiro sequence and more general pattern
sequences. In this paper we generalize these results to any polynomial
subsequence (instead of squares) and thereby answer an open problem of Sun and
Winterhof. We conclude this paper by some open problems.
